动态规划简单总结

发表于 | 分类于

解题步骤

动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。

下面我们先来讲下做动态规划题很重要的三个步骤：

第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？

第二步骤：找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。

第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。

由了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。

优化的时候，可以只记录状态转移方程的生成值，即 s[n-2] + s[n-1] = s[n],则记录 dp 的时候可以考虑只记录 2个值： prev curr ，这个技巧名为： 状态压缩

遍历方式

我们做动态规问题时，经常会对 dp 数组的遍历顺序有些头疼。我们拿二维 dp 数组来举例，有时候我们是正向遍历：

1
2
3
4
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        // 计算 dp[i][j]

有时候我们反向遍历：

1
2
3
for (int i = m - 1; i >= 0; i--)
    for (int j = n - 1; j >= 0; j--)
        // 计算 dp[i][j]

有时候可能会斜向遍历：

// 斜着遍历数组

1
2
3
4
5
6
for (int l = 2; l <= n; l++) {
    for (int i = 0; i <= n - l; i++) {
        int j = l + i - 1;
        // 计算 dp[i][j]
    }
}

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

遍历的终点必须是存储结果的那个位置。

其它

最优子结构性质作为动态规划问题的必要条件，一定是让你求最值的，以后碰到求最值题，思路往动态规划想就对了。

用空间换时间的思路，是降低时间复杂度的最通用技巧

计算机解决问题的解决办法就是大部分都是穷举，穷举所有可能性。算法设计就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。