动态规划（自底向上）

• 动态规划三要素：重叠子问题、最优子结构、状态转移方程

1. • 重叠子问题：备忘录、dp table
   • 最优子结构：子问题间必须互相独立
   • 状态转移方程书写套路：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

状态：原问题和子问题中会变化的变量

选择：导致「状态」产生变化的行为

  dp数组的含义对于问题的处理起着关键的作用，需要积累。如果dp数组的含义不得当或者不够清晰，会阻碍之后的步骤。

reference：这里

• 将dp table降维：将二维数组「投影」到一维数组

难点在于如何处理投影过程中被覆盖的值。

• • 想把二维 dp 数组压缩成一维，一般来说是把第一个维度，也就是 i 这个维度去掉，只剩下 j 这个维度。然后一定要画出dp table，在图上找出求dp[i][j]时的依赖关系，手动模拟各量的变化情况，找出如何提前将被覆盖的值保存起来的方法。
  • 对于base case也需投影。

reference：这里

• 如何消除重叠子问题：备忘录、dp table