一流的做pc端网站北京seo服务行者
题目与题解
参考资料：动态规划基础
动态规划五步曲
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导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;}
}看完代码随想录之后的想法
按照随想录的五步法做练习：
- 确定dp数组（dp table）以及下标的含义：dp[i]表示数i的斐波那契数
- 确定递推公式：题目已经给了，dp[i]=dp[i-1]+dp[i-2]
- dp数组如何初始化：同样题目已经给了，dp[0] = 0, dp[1] = 1
- 确定遍历顺序：当前数的斐波那契数由其前两个数相加直接得到，所以按顺序遍历即可
- 举例推导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就可以上去。所以做错的时候直接举例最直观。
今日收获
初步学习了动态规划方法的五部曲，用简单题实践了一下，目前感觉尚可。