代码随想录算法训练营第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）举例推导