动态规划

1、遍历的过程中，所需的状态必须是已经计算出来的。

2、遍历结束后，存储结果的那个位置必须已经被计算出来。

对动态规划进行降维打击

dp定义：

• 子序列问题定义：

  dp[i]：以num[i]为结尾的值

优化：

• 空间：滚动数组优化

  多开一个位置，然后%，可以减少rotate的时间，时间空间优化很大

  如果仅以来于上一层，甚至可以滚动数组都无需开，但是需要注意顺序：

  • 倒序更新，如01背包问题、三角形路径问题
  • 正序更新，如完全背包问题、矩阵路径问题

• 时间：斜率优化

动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。前者的递推性质还有一个名字，叫做 「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。