阅读 63

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

导言

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


切题套路

首先我们需要明确一个问题,那就是如何确定一个问题能够使用动态规划来解?之前的动态规划文章中,我们清楚知道这些例题就是要用动态规划求解,因此不会去考虑其它的算法或思想。那怎么通过一道题的题目描述确定这道题适不适合用动态规划解呢? 这里我不想讲特别理论的东西,比如最优子结构,重叠子问题,不讲并不代表这些概念不重要,而是说这些东西有时候并不是很容易从题目描述中简单推得,特别是在面试这种紧张的状态下。如果你仔细观察我们之前解过的所有动态规划相关的题目,题目无外乎下面几种问法:

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

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

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

  • 找出所有的方案(比如,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% 以上的动态规划相关问题都可以很好解决,当然了,要想达到熟能生巧的程度,还是需要多加练习,多思考,多对比,多总结,不然的话,学到的东西很快就会忘记。最后的最后,希望动态规划不再是你面试中的拦路虎,看到它,也希望你能多一份亲切和自信

关注下面的标签,发现更多相似文章
评论