网站建设一般多少钱官网,网络科技服务有限公司,柳州网站制作服务商,wordpress小工具九宫格题目链接#xff1a;509. 斐波那契数 代码随想录 视频#xff1a;手把手带你入门动态规划 | LeetCode#xff1a;509.斐波那契数_哔哩哔哩_bilibili 看完代码随想录之后的想法#xff1a;
我们要知道动态规划的五部曲#xff1b;
1#xff0c;确定dp数组的含义#x…题目链接509. 斐波那契数 代码随想录 视频手把手带你入门动态规划 | LeetCode509.斐波那契数_哔哩哔哩_bilibili 看完代码随想录之后的想法
我们要知道动态规划的五部曲
1确定dp数组的含义下标的含义
2确定递推公式
3确定dp数组如何初始化
4确定遍历顺序
5打印dp数组用来debug
1这道题目dp数组是第i位斐波那契数的值i是第i位
2dp[i] dp[i - 1] dp[i - 2];
3dp[0] 0,dp[1] 1;
4从前向后遍历
5可以打印数组debug
class Solution {public int fib(int n) {int[] dp new int[31];dp[0] 0;dp[1] 1;for(int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}
题目链接70. 爬楼梯 代码随想录 视频带你学透动态规划-爬楼梯对应力扣70.爬楼梯| 动态规划经典入门题目_哔哩哔哩_bilibili 看完代码随想录之后的想法
我们要知道动态规划的五部曲
1确定dp数组的含义下标的含义
2确定递推公式
3确定dp数组如何初始化
4确定遍历顺序
5打印dp数组用来debug
1dp[i]表示到达第i个台阶有dp[i]个方法
2dp[i] dp[i - 1] dp[i - 2];到达第i个台阶需要的方法等于到达第i - 1 的方法数加上 到达第i - 2 的方法数
3dp[0] 没有意义dp[1] 1, dp[2] 2;
4从前向后遍历
5可以打印dp数组用来debug
class Solution {public int climbStairs(int n) {int[] dp new int[46];dp[1] 1;dp[2] 2;for(int i 3; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}
题目链接59.螺旋矩阵II 文章讲解代码随想录 视频讲解一入循环深似海 | LeetCode59.螺旋矩阵II 看完代码随想录之后的想法
我们要知道动态规划的五部曲
1确定dp数组的含义下标的含义
2确定递推公式
3确定dp数组如何初始化
4确定遍历顺序
5打印dp数组用来debug
1,dp[i] 的含义到达下标i的位置所需要的的di[i](最小花费)
2递推公式dp[i] Math.min((dp[i - 1] cost[i - 1]), dp[i - 2] cost[i - 2]);
dp[i] 的含义到达下标i的位置所需要的的最小花费
dp[i - 1] 的含义到达下标i - 1的位置所需要的的最小花费 加上第i-1向上的花费
dp[i - 2] 的含义到达下标i - 2的位置所需要的的最小花费 加上第i-2向上的花费
然后取最小值
class Solution {public int minCostClimbingStairs(int[] cost) {int n cost.length;int[] dp new int[1001];for(int i 2; i n; i)dp[i] Math.min((dp[i - 1] cost[i - 1]), dp[i - 2] cost[i - 2]);return dp[n];}
}
总结
昨天下午学了一会计组但是晚上没有学想要淘一个二手自行车今天开始动态规划的入门背了一个小时的英语单词
