动态规划

主要记录平常刷动态规划题目的一些简单的理解。

1.确定使用时机：

1.题目只要求返回结果，不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划」解决。

2.题目中有多个子问题/子过程。

2.定义子问题:

建议优先定义和原先问题一样的子问题，只不过是模型变小了一点。

3.优化子结构：

找出递推方程。也就是状态转移方程。

假设子问题的解设置为dp[i],那么递推方程一定是dp[i]和dp[i-1],nums[i]之间的关系。

无需考虑后面。因为后面的相当于是在下一次的时候变成前面。

但是有时候需要考虑dp[i-2]之类的。

4.写题：

5.二维数组：多状态：

当状态比较多的时候，可以使用dp[i] [j] 这样的状态转移方程，并经过多级分类讨论之后得出结果。

[j]一般是确定的状态，而且相对较少，比如包不包含最后一个数，是不是执行了某种动作，等等。