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

r囧r小猫 2023-06-27 11:16 64阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![format_png][]

作者 | P.yh

来源 | 五分钟学算法

### 导言 ###

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

### 切题套路 ###

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

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

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

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

*  最值问题（比如，最长公共子序列、最小编辑距离、背包能装的最大价值…）
 *  所有方案的个数（比如，两点之间路径个数、爬楼梯问题…）
 *  是否类问题（比如，两个字符串是否按一定方式匹配、背包是否能被填满…）

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

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

*  找出所有的方案（比如，N 皇后问题、求解一个集合的所有子集、排列组合类问题…）
 *  排序相关的问题（比如，滑动窗口类问题、双指针类问题…）
 *  极值类问题（比如，求数组当中的峰值…）

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

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

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

*  [动态规划之矩阵类动规 (考虑当前的子问题)][Link 1]
 *  [动态规划之序列类动规 (考虑之前的子问题)][Link 2]
 *  [动态规划之字符匹配类动规 (画表格)][Link 3]
 *  [动态规划之区间类动规 (倒着想)][Link 4]
 *  [动态规划之背包类动规 (按值定状态)][Link 5]

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

### 空间优化 - 滚动数组 ###

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

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% 以上的动态规划相关问题都可以很好解决。

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

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

**-----------------------**

**公众号：五分钟学算法****（ID：CXYxiaowu****）**

**博客：www.cxyxiaowu.com**

**知乎：程序员吴师兄**

**一个正在学习算法的人，致力于将算法讲清楚！**

长按下图二维码关注，和你一起领悟算法的魅力**。**

![format_png 1][]

**戳一下下方的小程序，24 小时一起学算法**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA?x-oss-process=image/format,png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e6239cd79eb2fe6e831d7debba60aa906721d592b8766a944ef88bf91bf82568c20d71891&idx=1&mid=2247486904&scene=21&sn=099d5560ab25c0163349dff0c7f51490#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e624acd79eb5cdb410808921609a830b9b9221e813e4eb89cf551ca48f317668d44b095d2&idx=2&mid=2247486923&scene=21&sn=6c1c8aeb4db68522e67ddf8c1e933660#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e6259cd79eb4f240786ad7c00dcd0ed39ad68fd62b72e15d6a8ee0ecbd26b6250ab3b1171&idx=1&mid=2247486936&scene=21&sn=27ec53c1463384edeeee138db23c1c7d#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e6186cd79e8907d12e96f831e9624dc5dfcc11428fad22b9e28877852706fbbfce835af9d&idx=1&mid=2247486983&scene=21&sn=478a07180b594d686c4040e82b1a72c4#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e6148cd79e85ea0e6bd48318d739871538d65258ed5d09e5df8ee5b63034534a3ef042cf3&idx=2&mid=2247487177&scene=21&sn=e38ffa48d090aff771dad31d7bc2ae25#wechat_redirect
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA?x-oss-process=image/format,png