[Vssue]动态规划理论基础.md

[youngyangyang04]

https://www.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

[Du1in9]

动态规划

动态规划（Dynamic Programming），简称 DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的。贪心和上一个状态没有关系，所以贪心解决不了动态规划的问题。

解题步骤

状态转移公式（递推公式）固然重要，但动态规划不仅仅只有递推公式。对于动态规划问题，我将拆解为如下五步曲：① 确定 dp 数组以及下标的含义；② 确定递推公式；③ dp 数组如何初始化；④ 确定遍历顺序；⑤ 举例推导 dp 数组。 为什么先确定递推公式，然后初始化 dp 数组？因为有时候是由递推公式决定了 dp 数组要如何初始化。

如何 debug

debug 的最好方式就是把 dp 数组打印出来，看看究竟是不是按照自己思路推导的。写代码之前一定要把状态转移在 dp 数组上的具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。