参考文献链接：代码随想录

本人代码是Java版本的，如有别的版本需要请上代码随想录网站查看。

509. 斐波那契数

力扣题目链接

解题思路

这道题目非常简单，用递归也能做的出来，代码随想录中选取这道题目来入门斐波那契数是为了讲清楚动态规划五部曲。

动态规划五部曲

第一步：确定dp[i]数组以及下标的含义

第二步：确定递归公式

第三步：确定数组如何初始化

第四步：确定遍历顺序

第五步：打印dp数组去debug

这道题目简单其实是因为题目中以及给了所有的东西，比如递归公式斐波那契数列的很明显，数组初始化题目中也说了第一个为0第二个为1。遍历顺序刚好又是从前往后，所以就很简单。

代码示例

class Solution {
    public int fib(int n) {
        if(n == 1){
            return 1;
        }
        if(n == 0){
            return 0;
        }
        int sum = 0;
        int first = 0;
        int second = 1;
        for(int i = 2;i <= n;i++){
            sum = first + second;
            first = second;
            second = sum;
        }
        return sum;
    }
}

70. 爬楼梯

力扣题目链接

解题思路

这道题目还是像上一题一样去思考。

第一：确认数组下标含义：代表每个楼梯有几种办法上去

第二：确认递推公式：每一个楼梯都等于前两个楼梯的和

第三：确认数组初始化：初始化前两个即可，第一个为1，第二个为2

第四：遍历顺序：顺序即可。

代码示例

class Solution {
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2;i < n;i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
}

746. 使用最小花费爬楼梯

力扣题目链接

解题思路

依然是五部曲。

第一步确认dp数组的含义，dp数组的含义是当爬到第i层时耗费的最少的钱

第二步确认递推公式，min(dp[i] = dp[i - 2] + cost[i - 2] ,dp[i] = dp[i - 2] + cost[i - 2])

第三步确认初始化，dp0和dp1都初始化为0，因为上第一层和第二层不需要钱

第四步顺序，那肯定是顺序遍历

代码示例

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2;i < dp.length;i++){
            int first = dp[i - 2] + cost[i - 2];
            int second = dp[i - 1] + cost[i - 1];
            dp[i] = first < second ? first : second;
        }
        return dp[dp.length - 1];
    }
}