网站建设与维护 唐清安,织梦html网站地图,制作网页小图片,做购物网站哪种服务器好题目与题解 参考资料#xff1a;动态规划基础 动态规划五步曲
确定dp数组#xff08;dp table#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
509. 斐波那契数 题目链接#xff1a;509. 斐波那契数 代码随想录题解动态规划基础 动态规划五步曲
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
509. 斐波那契数 题目链接509. 斐波那契数 代码随想录题解509. 斐波那契数 视频讲解手把手带你入门动态规划 | LeetCode509.斐波那契数_哔哩哔哩_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) {vectorint 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. 使用最小花费爬楼梯 视频讲解动态规划开更了| LeetCode746. 使用最小花费爬楼梯_哔哩哔哩_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就可以上去。所以做错的时候直接举例最直观。
今日收获 初步学习了动态规划方法的五部曲用简单题实践了一下目前感觉尚可。
