点击蓝色“
五分钟学算法
”关注我哟
加个“
星标
”，天天中午 12:15，一起学算法
作者 | P.yh
来源 | 五分钟学算法
导言
之前我们就动态规划问题进行了分类与讨论，这篇文章会讲解一些常见的动态规划题目分析技巧和套路，还有一个动态规划状态数组的空间优化技巧，并基于之前的文章进行总结。
切题套路
首先我们需要明确一个问题，那就是如何确定一个问题能够使用动态规划来解？
之前的动态规划文章中，我们清楚知道这些例题就是要用动态规划求解，因此不会去考虑其它的算法或思想。
那怎么通过一道题的题目描述确定这道题适不适合用动态规划解呢？
这里我不想讲特别理论的东西，比如最优子结构，重叠子问题，不讲并不代表这些概念不重要，而是说这些东西有时候并不是很容易从题目描述中简单推得，特别是在面试这种紧张的状态下。如果你仔细观察我们之前解过的所有动态规划相关的题目，题目无外乎下面几种问法：
-
最值问题（比如，最长公共子序列、最小编辑距离、背包能装的最大价值…）
-
所有方案的个数（比如，两点之间路径个数、爬楼梯问题…）
-
是否类问题（比如，两个字符串是否按一定方式匹配、背包是否能被填满…）
上面给出的几种问法都是动态规划题目很常见的问法，如果题目中含有这类信息，你就可以尝试着往动态规划的思路去思考，试着去拆解问题、定义状态等等，当然没有绝对，并不是说所有这种问法的题目都可以用动态规划解，只是大概率是这样，解题的时候多一个思考方向总不是坏事。
当然，还有些题目基本上不大可能使用动态规划求解：
这里我解释一下，上面的第一点 “
找出所有的方案
” 意思是让你列出所有的情况，而不是仅仅输出方案的个数，很多时候，这类题目的方案的总数是随着输入变量呈指数型增长的，因为要列出所有方案，因此再怎么优化，你的时间复杂度还是指数级别的，动态规划在这边起不到作用，这种题目往往会优先考虑使用
暴力的深度优先搜索
来求解。
第二点 “
排序相关的问题
”，有时这类问题的描述和动态规划题目的描述很像，比如最大滑动窗口，但这类题目区别于动态规划的地方在于，其答案往往并不是一个固定的数值，比如滑动窗口类问题最后让你输出的是一个数组，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
