动规是由前一个状态推导出来的，而贪心是局部直接选最优
对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

  • 确定dp数组（dp table）以及下标的含义
  • 确定递推公式
  • dp数组如何初始化
  • 确定遍历顺序
  • 举例推导dp数组

因为一些情况是递推公式决定了dp数组要如何初始化！

动态规划应该如何debug

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！
做动规的题目，写代码之前一定要把**状态转移在dp数组的上具体情况模拟一遍**，心中有数，确定最后推出的是想要的结果。
如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。
这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了。

  • 这道题目我举例推导状态转移公式了么？
  • 我打印dp数组的日志了么？
  • 打印出来了dp数组和我想的一样么？