代码随想录算法训练营第38天 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

本文主要是介绍代码随想录算法训练营第38天 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码随想录算法训练营第38天 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

  • 理论基础
  • 自己看到题目的第一想法
  • 看完代码随想录之后的想法

链接: 509. 斐波那契数
链接: 70. 爬楼梯
链接: 746. 使用最小花费爬楼梯

理论基础

五部曲:
1.确定dp数组(dp table)以及下标的含义
2.确定递推公式
3.dp数组如何初始化
4.确定遍历顺序
5.举例推导dp数组

自己看到题目的第一想法

509.斐波那契数:直接看题解。
70.爬楼梯:
746.使用最小花费爬楼梯:

看完代码随想录之后的想法

509.斐波那契数:
五部曲上秤!
(1)确定dp数组以及下标的含义:dp[i]的定义为:第i个数的斐波那契数值是dp[i]
(2)确定递推公式:直接有递推公式:状态转移方程dp[i]=dp[i-1]+dp[i-2]
(3)dp数组如何初始化:dp数组的初始化题目给了,dp[0]=0,dp[1]=1
(4)确定遍历顺序:从递归公式可以看出,dp[i]依赖dp[i-1]和dp[i-2],那么遍历顺序应当先确定前面的数再确定后面的数,所以是从前到后遍历。
(5)举例推导dp数组:根据递推公式推导举例,如果发现结果不对,就把dp数组打印出来看看推导的数列是否一致。
代码还是很简单的,可以使用
70.爬楼梯:
五部曲上秤!
(1)确定dp数组以及下标的含义:dp[i]的定义为:爬到第i层楼,有dp[i]种方法
(2)递推公式:dp[i]有两个方向可以推出来,dp[i-1]和dp[i-2],这里理解是一个难点,为什么可以这样推导,因为只能走1步或者2步,而没有其他方法上一步到这一步。所以dp[i]=dp[i-1]+dp[i-2]。
(3)dp数组如何初始化:dp[1]=1,dp[2]=2
(4)确定遍历顺序:从前向后遍历
(5)举例推导:如果代码有问题就把dp数组打印出来看与自己的举例是否一样。
746.使用最小花费爬楼梯:
五部曲上秤!
(1)确定dp数组以及下标的含义:dp[i]的定义为到位置i所需要的花费是多少。
(2)递推公式:有两个途径得到dp[i],一个是dp[i-1],一个是dp[i-2],有一个难想的点就是,究竟是从dp[i-1]跳还是从dp[i-2]跳呢?根据题意是需要最小的,那么就是dp[i]=min[dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])。
(3)如何初始化:dp[0]=0, dp[1]=0
(4)遍历顺序:从前向后遍历
(5)举例推导

这篇关于代码随想录算法训练营第38天 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1018853

相关文章

使用Docker构建Python Flask程序的详细教程

《使用Docker构建PythonFlask程序的详细教程》在当今的软件开发领域,容器化技术正变得越来越流行,而Docker无疑是其中的佼佼者,本文我们就来聊聊如何使用Docker构建一个简单的Py... 目录引言一、准备工作二、创建 Flask 应用程序三、创建 dockerfile四、构建 Docker

Python使用vllm处理多模态数据的预处理技巧

《Python使用vllm处理多模态数据的预处理技巧》本文深入探讨了在Python环境下使用vLLM处理多模态数据的预处理技巧,我们将从基础概念出发,详细讲解文本、图像、音频等多模态数据的预处理方法,... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

C#中Guid类使用小结

《C#中Guid类使用小结》本文主要介绍了C#中Guid类用于生成和操作128位的唯一标识符,用于数据库主键及分布式系统,支持通过NewGuid、Parse等方法生成,感兴趣的可以了解一下... 目录前言一、什么是 Guid二、生成 Guid1. 使用 Guid.NewGuid() 方法2. 从字符串创建

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

Spring IoC 容器的使用详解(最新整理)

《SpringIoC容器的使用详解(最新整理)》文章介绍了Spring框架中的应用分层思想与IoC容器原理,通过分层解耦业务逻辑、数据访问等模块,IoC容器利用@Component注解管理Bean... 目录1. 应用分层2. IoC 的介绍3. IoC 容器的使用3.1. bean 的存储3.2. 方法注

Python内置函数之classmethod函数使用详解

《Python内置函数之classmethod函数使用详解》:本文主要介绍Python内置函数之classmethod函数使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 类方法定义与基本语法2. 类方法 vs 实例方法 vs 静态方法3. 核心特性与用法(1编程客