动态规划

思路

TIP

如果某一问题有很多重叠子问题，使用动态规划是最有效的。

代码随想录 定义的动态规划五部曲：

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

基础问题

• 746. 使用最小花费爬楼梯
  • dpi = Math.min(dp1 + cost[i-1], dp0 + cost[i-2])
  • 注意这题的空间优化方法，由于只用到 dp 数组的前两个，因此不需要创建一个数组保存所有值，只需要保存前两个就可以了。
• 343. 整数拆分
  • 从那个数开始初始化、边界条件等等，需要再仔细考虑考虑。

背包问题