动态规划之空间优化与总结回顾

导言

之前我们就动态规划问题进行了分类与讨论，这篇文章会讲解一些常见的动态规划题目分析技巧和套路，还有一个动态规划状态数组的空间优化技巧，并基于之前的文章进行总结。

切题套路

首先我们需要明确一个问题，那就是如何确定一个问题能够使用动态规划来解？

之前的动态规划文章中，我们清楚知道这些例题就是要用动态规划求解，因此不会去考虑其它的算法或思想。

那怎么通过一道题的题目描述确定这道题适不适合用动态规划解呢？

这里我不想讲特别理论的东西，比如最优子结构，重叠子问题，不讲并不代表这些概念不重要，而是说这些东西有时候并不是很容易从题目描述中简单推得，特别是在面试这种紧张的状态下。如果你仔细观察我们之前解过的所有动态规划相关的题目，题目无外乎下面几种问法：

• 最值问题（比如，最长公共子序列、最小编辑距离、背包能装的最大价值…）

• 所有方案的个数（比如，两点之间路径个数、爬楼梯问题…）

• 是否类问题（比如，两个字符串是否按一定方式匹配、背包是否能被填满…）

上面给出的几种问法都是动态规划题目很常见的问法，如果题目中含有这类信息，你就可以尝试着往动态规划的思路去思考，试着去拆解问题、定义状态等等，当然没有绝对，并不是说所有这种问法的题目都可以用动态规划解，只是大概率是这样，解题的时候多一个思考方向总不是坏事。

当然，还有些题目基本上不大可能使用动态规划求解：

• 找出所有的方案（比如，N 皇后问题、求解一个集合的所有子集、排列组合类问题…）

• 排序相关的问题（比如，滑动窗口类问题、双指针类问题…）

• 极值类问题（比如，求数组当中的峰值…）

这里我解释一下，上面的第一点 “找出所有的方案” 意思是让你列出所有的情况，而不是仅仅输出方案的个数，很多时候，这类题目的方案的总数是随着输入变量呈指数型增长的，因为要列出所有方案，因此再怎么优化，你的时间复杂度还是指数级别的，动态规划在这边起不到作用，这种题目往往会优先考虑使用 暴力的深度优先搜索 来求解。

第二点 “排序相关的问题”，有时这类问题的描述和动态规划题目的描述很像，比如最大滑动窗口，但这类题目区别于动态规划的地方在于，其答案往往并不是一个固定的数值，比如滑动窗口类问题最后让你输出的是一个数组，Two Sum 相关的问题最后也是让你找到匹配的元素，对于这些问题都有固定的套路，在这我就不过多赘述了。最后一点 极值类问题，这类问题出现的频率不是很高，但是你还是需要将其和最值类问题区分开来对待。

在这里，我列出了我们之前讲解的动态规划的几种题型:

• 动态规划之矩阵类动规 (考虑当前的子问题)

• 动态规划之序列类动规 (考虑之前的子问题)

• 动态规划之字符匹配类动规 (画表格)

• 动态规划之区间类动规 (倒着想)

• 动态规划之背包类动规 (按值定状态)

上面括号中是针对对应题型的思考方向和分析策略，你也可以回顾下这些内容，分析一下这些动态规划题型的相同和不同之处，加深一下理解。

空间优化 – 滚动数组

有一个比较通用的空间优化技巧没有在之前的文章中提到，很多的动态规划题目都可以套用这个技巧，我们就拿之前的 最长公共子序列 这道题目来举例说明，当时我们最终实现的代码是这样的：

public int longestCommonSubsequence(String text1, String text2) {
    int length1 = text1.length();
    int length2 = text2.length();

    int[][] dp = new int[length1 + 1][length2 + 1];

    char[] textArr1 = text1.toCharArray();
    char[] textArr2 = text2.toCharArray();

    for (int i = 1; i <= length1; ++i) {
        for (int j = 1; j <= length2; ++j) {
            if (textArr1[i - 1] == textArr2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[length1][length2];
}

你仔细观察代码，会发现当前考虑的状态 dp[i][j] 仅仅依赖于 dp[i - 1][j] 和 dp[i][j - 1]，如果画出表格，也就是当前行的格子只会和当前行以及前一行的格子有关，因此，保留两行数据就能够满足状态迭代更新的要求，我们可以得到下面的代码：

public int longestCommonSubsequence(String text1, String text2) {
    int length1 = text1.length();
    int length2 = text2.length();

    int[][] dp = new int[2][length2 + 1];

    char[] textArr1 = text1.toCharArray();
    char[] textArr2 = text2.toCharArray();

    for (int i = 1; i <= length1; ++i) {
        for (int j = 1; j <= length2; ++j) {
            if (textArr1[i - 1] == textArr2[j - 1]) {
                dp[i%2][j] = dp[(i - 1)%2][j - 1] + 1;
            } else {
                dp[i%2][j] = Math.max(dp[(i - 1)%2][j], dp[i%2][j - 1]);
            }
        }
    }

    return dp[length1%2][length2];
}

这里我们成功将空间的维度降低了一维，当然如果你觉得取模的操作让代码变得不整洁，你也可以参考下面的代码：

public int longestCommonSubsequence(String text1, String text2) {
    int length1 = text1.length();
    int length2 = text2.length();

    int[][] dp = new int[2][length2 + 1];

    char[] textArr1 = text1.toCharArray();
    char[] textArr2 = text2.toCharArray();

    int cur = 0, prev = 1;
    for (int i = 1; i <= length1; ++i) {
        prev = cur; cur = 1 - cur;
        for (int j = 1; j <= length2; ++j) {
            if (textArr1[i - 1] == textArr2[j - 1]) {
                dp[cur][j] = dp[prev][j - 1] + 1;
            } else {
                dp[cur][j] = Math.max(dp[prev][j], dp[cur][j - 1]);
            }
        }
    }

    return dp[cur][length2];
}

其实滚动数组的思想不难理解，就是只保存需要用到的子问题的答案（状态），覆盖那些不需要用到的子问题的答案，状态在同一块空间中不断翻滚迭代向前。

当然，有些动态规划的实现方式就不太容易使用这类优化，比如 记忆化搜索，还有些动态规划题型，比如 区间类动态规划，状态的更新不是逐行逐列的，使用滚动数组来优化也不是特别容易，因此使用滚动数组优化的时候还是需要结合实际情况考虑。

滚动数组一般来说都可以将状态数组的空间降低一维，比如三维变二维、二维变一维、一维变常数，当然有些具体题型的空间优化也可以做到这个，比如背包类型的动态规划问题中，我们通过改变遍历的顺序，直接就可以做到空间降维，但其实这是这类动态规划问题特有的优化，不属于滚动数组的范畴。

总结

动态规划系列内容算是结束了，虽然有关动态规划的知识点还有很多，但是我相信如果深刻掌握并理解了之前我们讲的内容，基本上 leetcode 上面 90% 以上的动态规划相关问题都可以很好解决。

当然了，要想达到熟能生巧的程度，还是需要多加练习，多思考，多对比，多总结，不然的话，学到的东西很快就会忘记。

最后的最后，希望动态规划不再是你面试中的拦路虎，看到它，也希望你能多一份亲切和自信。