赞
踩
题目链接:509. 斐波那契数
文档讲解:代码随想录/斐波那契数
视频讲解:视频讲解-斐波那契数
状态:已完成(1遍)
虽然看了卡哥的动态规划五部曲,但是看到题目之后还是不太会操作索性不要有自己多余的思考了,直接看视频讲解。
用动态规划五部曲:
按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2],我们来推导一下,当N为10的时候,dp数组应该是如下的数列:0 1 1 2 3 5 8 13 21 34 55。
看了讲解手搓代码如下:
- /**
- * @param {number} n
- * @return {number}
- */
- var fib = function(n) {
- let dp = [];
- dp[0] = 0,dp[1] = 1;
- for(let i = 2;i<=n;i++){
- dp[i] = dp[i-1] + dp[i-2];
- }
- return dp[n];
- };
这道题作为动态规划之所以简单,是因为递推公式、初始化、遍历顺序都已经由题目确定。
题目链接:70. 爬楼梯
文档讲解:代码随想录/爬楼梯
视频讲解:视频讲解-爬楼梯
状态:已完成(1遍)
用动态规划五部曲:
按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2],我们来推导一下,dp数组应该是如下的数列: 1 1 2 3 5 8 13 21 34 55。
手搓代码如下:
- /**
- * @param {number} n
- * @return {number}
- */
- var climbStairs = function(n) {
- let dp = [1,1];
- for(let i =2;i<=n;i++){
- dp[i] = dp[i-1] + dp[i-2];
- }
- return dp[n];
- };
提交成功!
严格遵守对dp[i]的描述,直接没有i=0的时候。
讲解代码如下:
- /**
- * @param {number} n
- * @return {number}
- */
- var climbStairs = function(n) {
- // dp[i] 为第 i 阶楼梯有多少种方法爬到楼顶
- // dp[i] = dp[i - 1] + dp[i - 2]
- let dp = [1 , 2]
- for(let i = 2; i < n; i++) {
- dp[i] = dp[i - 1] + dp[i - 2]
- }
- return dp[n - 1]
- };
一开始我就往动态规划的思路上靠,感觉既然只有两种行走方式,那到dp[i]级阶梯的方式肯定就是他的下一级dp[i-1]和下两级dp[i-2],所以到这级阶梯的方式就是到下两级阶梯方式的和。
题目链接:746. 使用最小花费爬楼梯
文档讲解:代码随想录/使用最小花费爬楼梯
视频讲解:视频讲解-使用最小花费爬楼梯
状态:已完成(1遍)
用动态规划五部曲:
按照这个递推公式我们来推导一下,dp数组应该是如下的数列: 10 15 30 。
手搓代码如下:
- /**
- * @param {number[]} cost
- * @return {number}
- */
- var minCostClimbingStairs = function(cost) {
- let dp = [cost[0],cost[1]];
- for(let i =2;i<cost.length;i++){
- dp[i] = Math.min(dp[i - 1],dp[i - 2]) + cost[i];
- }
- return Math.min(dp[cost.length-1],dp[cost.length-2]);
- };
提交成功,没有问题。 我在求最后一级阶梯的时候就不用走for循环里了,直接比较从前两节阶梯哪个出发更便宜。
卡尔哥用dp[i]表示到达第i节阶梯的最便宜花费,确实省事一点。
讲解代码如下:
- /**
- * @param {number[]} cost
- * @return {number}
- */
- var minCostClimbingStairs = function(cost) {
- const dp = [0, 0]
- for (let i = 2; i <= cost.length; ++i) {
- dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
- }
- return dp[cost.length]
- };
今天的三道题还算简单,希望明后天可以撑住。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。