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

题目与题解

参考资料：动态规划基础

动态规划五步曲 

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

509. 斐波那契数

题目链接：​​​​​​​509. 斐波那契数

代码随想录题解：509. 斐波那契数

视频讲解：手把手带你入门动态规划 | LeetCode：509.斐波那契数_哔哩哔哩_bilibili

解题思路：

        斐波那契数是最经典的递归/迭代题，迭代方法对应的就是动态规划。

        已知F(0), F(1)以及F(n) = F(n-1)+F(n-2)，直接就可以用循环逐一写出F(n)的值了。这里因为不需要求1-n之间每个数的斐波那契数，所以简单一点，不用数组记录结果，只要用临时变量记录F(n-1)和F(n-2)即可。

class Solution {
    public int fib(int n) {
		if (n <= 1) return n;
		int pre1 = 0, pre2 = 1;
		int cur = 0;
		for (int i = 2; i < n; i++) {
			cur = pre1 + pre2;
			pre1 = pre2;
			pre2 = cur;
		}
		return cur;
    }
}

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

        按照随想录的五步法做练习：

1. 确定dp数组（dp table）以及下标的含义：dp[i]表示数i的斐波那契数
2. 确定递推公式：题目已经给了，dp[i]=dp[i-1]+dp[i-2]
3. dp数组如何初始化：同样题目已经给了，dp[0] = 0, dp[1] = 1
4. 确定遍历顺序：当前数的斐波那契数由其前两个数相加直接得到，所以按顺序遍历即可
5. 举例推导dp数组：随意用一串斐波那契数带入递推公式 - 0,1,1,2,3,5,8...，符合要求

遇到的困难

        无

70. 爬楼梯

题目链接：​​​​​​​70. 爬楼梯

代码随想录题解：70. 爬楼梯

视频讲解：带你学透动态规划-爬楼梯（对应力扣70.爬楼梯）| 动态规划经典入门题目_哔哩哔哩_bilibili

解题思路：

        这题其实其实就是求斐波那契数的变种，因为爬到当前楼梯的方法，要么是从前一个楼梯爬一级，要么是从再前一个楼梯爬两级，除此之外没有别的选择了，所以递推公式仍然是F(n) = F(n-1)+F(n-2)，不一样的地方在于初始值，第一个数F(1)=1，第二个数F(2)=2。

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

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

        附上拓展题，一次最多可以爬m个台阶

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) { // 把m换成2，就可以AC爬楼梯这道题
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};

遇到的困难

        无

746. 使用最小花费爬楼梯 

题目链接：746. 使用最小花费爬楼梯 

代码随想录题解：​​​​​​​746. 使用最小花费爬楼梯 

视频讲解：动态规划开更了！| LeetCode：746. 使用最小花费爬楼梯_哔哩哔哩_bilibili

解题思路：

        这题比普通爬楼梯略复杂了一些，除了一次可以爬一步或者两步的基础要求外，还有需要花费最小代价，所以爬楼梯时哪些台阶走一步，哪些台阶走两步，就涉及到了选择的问题。但是，这里还是可以抽象化为动态规划去做，用dp[i]记录爬到当前台阶所需的最小花费，那么dp[i]要么是从dp[i-1]走一步得到，要么是从dp[i-2]走两步得到，所以dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])。

        这里需要注意一下，爬上第0级和第1级台阶是不需要代价的，所以初始化dp[0]=dp[1]=0。

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

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

        思路是一样的，这题同样不难，不严格按照五步分析也能写出来。但是后面题目变难了就不好说了。

遇到的困难

        一开始初始化dp[0]和dp[1]的时候写成了cost[0]cost[1]，怎么着都不对，然后就用了一个数列举例，逐一写出如何得到dp[i]的结果，然后才意识到第0,1级台阶不需要cost就可以上去。所以做错的时候直接举例最直观。

今日收获

        初步学习了动态规划方法的五部曲，用简单题实践了一下，目前感觉尚可。