本文最后更新于 2024-04-04,文章内容可能已经过时。

动态规划

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

1.确定使用时机:

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

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

2.定义子问题:

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

3.优化子结构:

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

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

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

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

4.写题:

5.二维数组:多状态:

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

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