自己做网站卖什么名字,哪些网站可以做直播,国家企业信用系统年报入口,火车票网站建设509. 斐波那契数
题目链接#xff1a;509. 斐波那契数 文档讲解#xff1a;代码随想录/斐波那契数 视频讲解#xff1a;视频讲解-斐波那契数 状态#xff1a;已完成#xff08;1遍#xff09; 解题过程
看到题目的第一想法
虽然看了卡哥的动态规划五部曲#xff0c;…509. 斐波那契数
题目链接509. 斐波那契数 文档讲解代码随想录/斐波那契数 视频讲解视频讲解-斐波那契数 状态已完成1遍 解题过程
看到题目的第一想法
虽然看了卡哥的动态规划五部曲但是看到题目之后还是不太会操作索性不要有自己多余的思考了直接看视频讲解。
看完代码随想录之后的想法
用动态规划五部曲
确定dp数组以及下标的含义dp[i]的定义为第i个数的斐波那契数值是dp[i]确定递推公式dp[i] dp[i - 1] dp[i - 2];dp数组如何初始化dp[0] 0 、dp[1] 1;确定遍历顺序从递归公式dp[i] dp[i - 1] dp[i - 2];中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的举例推导dp数组 按照这个递推公式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;in;i){dp[i] dp[i-1] dp[i-2];}return dp[n];
};
总结
这道题作为动态规划之所以简单是因为递推公式、初始化、遍历顺序都已经由题目确定。 70. 爬楼梯
题目链接70. 爬楼梯 文档讲解代码随想录/爬楼梯 视频讲解视频讲解-爬楼梯 状态已完成1遍 解题过程
看到题目的第一想法
用动态规划五部曲
确定dp数组以及下标的含义dp[i]的定义为到第i层阶梯有dp[i]种方式能够来到确定递推公式dp[i] dp[i - 1] dp[i - 2];dp数组如何初始化dp[0] 1 、dp[1] 1、dp[2] 2;确定遍历顺序从递归公式dp[i] dp[i - 1] dp[i - 2];中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的举例推导dp数组 按照这个递推公式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;in;i){dp[i] dp[i-1] dp[i-2];}return dp[n];
};
提交成功 看完代码随想录之后的想法
严格遵守对dp[i]的描述直接没有i0的时候。
讲解代码如下
/*** 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. 使用最小花费爬楼梯
题目链接746. 使用最小花费爬楼梯 文档讲解代码随想录/使用最小花费爬楼梯 视频讲解视频讲解-使用最小花费爬楼梯 状态已完成1遍 解题过程
看到题目的第一想法
用动态规划五部曲
确定dp数组以及下标的含义dp[i]的定义为从第i层阶梯出发的最小花费dp[i]元确定递推公式dp[i] dp[i - 1] 和 dp[i - 2] 的最小值 cost[i];dp数组如何初始化dp[0] cost[0] 、dp[1] cost[1] ;确定遍历顺序从递归公式中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的举例推导dp数组 按照这个递推公式我们来推导一下dp数组应该是如下的数列 10 15 30 。
手搓代码如下
/*** param {number[]} cost* return {number}*/
var minCostClimbingStairs function(cost) {let dp [cost[0],cost[1]];for(let i 2;icost.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]
};
总结
今天的三道题还算简单希望明后天可以撑住。
