Dynamic Programming I

动归思想在于重复利用已有结果来构造新结果。核心在于写出递推式，类似于induction中第i+1 case和第i case是什么关系。它可以看成是记忆化DFS暴力解，只是DFS的目标不是有数据结构的实体树，而是解空间构成的虚树。

初学者有时容易把动归和贪心弄混，动归和分治一样，都是利已有用局部最优解能得出全局最优解，它们的每个解是往后看，从已有解拼出来的，因此是全局最优；贪心是向前看，是局部最优，只有特定情况下局部最优才是全局最优。

本章主要考虑简单的DP问题，尤其是解空间是一维向量的情况。

看到是求不是树上，有某性质有多少数目的而不是求每个究竟是什么的一般都是DP。

做题套路：

1. 声明一个数组f，f的每个元素用来存到对应的那个位置时解是多少。

2. 初始化数组和i = 0时的情况. 如果f是二维的一般要初始第一行和第一列。

3. 遍历利用已知结果f[i-1]等求f[i]

4. 返回f[n - 1]

还有一个变种用法用于全局解无法直接用f[i-1]等求出，比如对于i的全局最优需要具体知道前面哪些nums元素组成才能重新算出，而f只存了最优值没有具体元素信息。这时f含义要变一下，不用来直接表示到那个位置时全局解是多少，而是包含nums[i]时解能是多少。相应返回值也不能是f[n-1]，而需要用一个全局变量存储时刻存储当前的全局最优。

即使input是一维，f也可能是二维的。尤其是求满足某个性质的substr是多少。f[i][j]表示substr(i,j)是否满足性质。