代码随想录算法训练营第三十二天| 509. 斐波那契数 、70. 爬楼梯、746. 使用最小花费爬楼梯 。c++转java

理论基础

总结一下就是：

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

动态规划五部曲

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

509. 斐波那契数

1.递归

class Solution {
    public int fib(int n) {
        if(n == 0 || n == 1)
            return n;
        return fib(n - 1) + fib(n - 2);
    }
}

2.dp

先按照动态规划的五部曲

1.确定dp数组以及下标的含义：dp数组表示的就是Fn，其中dp[i] = Fi.

2.确定递归公式：F(n) = F(n - 1) + F(n - 2).

3.dp数组的初始化：dp[0] = 0,dp[1] = 1.

4.确定遍历顺序：2~n.

5.举例推导dp数组：dp[2] = dp[1] + dp[0] = 1.

可以写出下面代码：

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

但是对于这道题，其实我们只需要用到最后的dp[n],所以代码可以改为：

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

70. 爬楼梯

思路：可以跟上面一样用递归，或者dp做，dp分析如下:

1.dp数组表示的是从第一节台阶到第n个台阶的方式数，dp[i]表示的是从1~i有多少种走法。

2.递推公式：dp[i] = dp[i - 1] + dp[i - 2]。

3.dp数组的初始化：dp[1] = 1,dp[2] = 2;

4.遍历顺序：3~n

5.举例推导递推公式：dp[3] = dp[2] + dp[1];

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

746. 使用最小花费爬楼梯

思路：还是使用五部曲进行分析，但是这里特殊的一点就是，最后for循环里我们只算到了cost.length处，还没有到达顶部，可以在最后的时候比较一下，倒数第一步和倒数第二步，哪个更少，取一个min就是result了。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        if(cost.length == 2)
            return Math.min(cost[0],cost[1]);
        int[] dp = new int[2];
        dp[0] = cost[0];
        dp[1] = cost[1];
        int res = 0;
        for(int i = 2;i < cost.length;i++){
            res = cost[i] + Math.min(dp[0],dp[1]);
            dp[0] = dp[1];
            dp[1] = res;
        }
        res = Math.min(res,dp[0]);
        return res;
    }
}

总结：五部曲确实很好用，可以分析得也更透彻(๑•̀ㅂ•́)و✧