代码随想录算法训练营第三十八天 | ● 理论基础 ● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯

题目链接：509. 斐波那契数 

代码随想录

视频：手把手带你入门动态规划 | LeetCode：509.斐波那契数_哔哩哔哩_bilibili

看完代码随想录之后的想法：

我们要知道动态规划的五部曲；

1，确定dp数组的含义，下标的含义；

2，确定递推公式；

3，确定dp数组如何初始化；

4，确定遍历顺序；

5，打印dp数组（用来debug）；

1这道题目dp数组是第i位斐波那契数的值，i是第i位

2，dp[i] = dp[i - 1] + dp[i - 2];

3，dp[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）

1，dp[i]表示到达第i个台阶有dp[i]个方法；

2，dp[i] = dp[i - 1] + dp[i - 2];到达第i个台阶需要的方法等于到达第i - 1 的方法数加上 到达第i - 2 的方法数

3，dp[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

文章讲解：代码随想录

视频讲解：一入循环深似海 | LeetCode：59.螺旋矩阵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];}
}

总结：

昨天下午学了一会计组，但是晚上没有学，想要淘一个二手自行车，今天开始动态规划的入门，背了一个小时的英语单词；