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

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

动态规划理论基础

动态规划理论基础
文章讲解：https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
视频讲解：https://www.bilibili.com/video/BV13Q4y197Wg

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

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

动态规划五步骤：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 打印dp数组

自己实现过程中遇到哪些困难

斐波那契数

509. 斐波那契数
文章讲解：https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html
题目链接：https://leetcode.cn/problems/fibonacci-number/
视频讲解：https://www.bilibili.com/video/BV1f5411K7mo/

自己看到题目的第一想法

斐波那契数列，S(n) = S(n - 1) + S(n-2)，可以用递归去处理。这里主要学习用动态规划的思路去处理。

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

动态规划五步骤：

• 确定dp数组（dp table）以及下标的含义
  • 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数组
  • 我们来推导一下，当N为10的时候，dp数组应该是如下的数列：0 1 1 2 3 5 8 13 21 34 55

自己实现过程中遇到哪些困难

按照动态规划五步骤处理业务逻辑比较简单，这里需要关注的就是边界条件的处理。边界条件未处理导致未一次ac。

爬楼梯

70. 爬楼梯
文章讲解：https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html
题目链接：https://leetcode.cn/problems/climbing-stairs/
视频讲解：https://www.bilibili.com/video/BV17h411h7UH/

自己看到题目的第一想法

可以同递归去处理，但是这里可以试试递归五步骤。
动态规划五步骤：

• 确定dp数组（dp table）以及下标的含义
  • dp[i]的定义为：第i个台阶爬到顶楼的方法数量
• 确定递推公式
  • 当给定台阶n时，n-1只能走一步到n，方法数是f(n-1)。n-2只能走2步到n的方法数是f(n-2)。因此f(n)=f(n-1) + f(n-2)
• dp数组如何初始化
  • 题目中把如何初始化也直接给我们了，dp[1] = 1;dp[2] = 2;
• 确定遍历顺序
  • 爬楼梯是从下往上爬的因此i从小到大
• 打印dp数组
  • 我们来推导一下，当N为3的时候，dp数组应该是如下的数列：1,2,3。为4时1,2,3,5。

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

一样的处理逻辑，n-1个台阶方法数是f(n-1)，n-2走2步到fn因此n-2为f(n-2)。因此f(n) = f(n-1) + f(n-2)。

自己实现过程中遇到哪些困难

使用最小花费爬楼梯

746. 使用最小花费爬楼梯
文章讲解：https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html
题目链接：https://leetcode.cn/problems/min-cost-climbing-stairs/
视频讲解：https://www.bilibili.com/video/BV16G411c7yZ/

自己看到题目的第一想法

动态规划五步骤：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 打印dp数组

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

动态规划五步骤：

• 确定dp数组（dp table）以及下标的含义
  • dp[i] 为第i个台阶的最小花费
• 确定递推公式
  • dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2])
• dp数组如何初始化
  • dp[0] = 0; dp[1] = 0;
• 确定遍历顺序
  • 从小到大遍历
• 打印dp数组

自己实现过程中遇到哪些困难

无，该题目核心就是确定递推公式，递推公式需要考虑最小值。

今日收获&学习时长

学习了动态规划五步骤：

1. 确定dp数组以及下标含义
2. 确定递推公式
3. 确定初始化值
4. 确定遍历顺序
5. 打印dp数组，check结果

学习时长：
2小时