算法 | 动态规划实战，最长公共子序列
题目：最长公共子序列。给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。如果不存在公共子序列，就返回 0。“子序列”里的字符可以不连续，但在原字符串中的相对顺序不能变。
假设字符串 text1 = "abcabcdbdxe"，text2 = "xabcde"。
先朴素，再优化
先用朴素的算法，梳理下问题的状态和状态空间。
思路：依次扫描 text2，在 text1 中找以 text2[i] 开头的最长公共子序列。
以 x 开头
先看 text2[0]="x" 字符。在 text1 中找到了一处 x，位于下标 9。如下图：
然后从 text1 的下标 10 开始（含），依次匹配 text2 里的剩余字符。我们发现 text2[1]="a", text2[2]="b", text2[3]="c", text2[4]="d" 均没有找到相同的，只有 text2[5]="e" 在下标 10 处匹配到了。如下图：
所以，以 text2[0]="x" 开头的最长公共子序列就是字符串 "xe"，长度为 2。
以 a 开头
再来看 text2[1]="a" 字符。在 text1 中找到了两处字符 a，分别位于下标 0 和下标 3。如下图：
同理，再从相应的位置开始，继续匹配 text2 里的剩余字符 b, c, d, e。
先看第一处的 a
第一处的 a 位于 text1 的下标 0，所以从 text1 的下标 1 开始（含）找字符 b，找到了三处。如下图：
再继续找下一个字符 c。在第一处的 b 后面找到了两个 c，在第二处的 b 后面找到了一个 c，在第三处的 b 后面没有找到字符 c。如下图：
再继续找下一个字符 d，结果如下图所示：
再继续找最后一个字符 e，结果如下图所示：
至此，以 text2[1]=text1[0]="a" 开头的最长公共子序列找到了 7 个，分别是 6 个 "abcde" 和 1 个 "abde"，显然最长长度是 5。
再看第二处的 a
第二个 a 位于 text1[3]。
同理，继续找下一个字符 b，结果如下图：
再依次找剩余的字符 c, d, e，最终结果为下图：
至此，以 text2[1]=text1[3]="a" 开头的最长公共子序列找到了 3 个，分别是 2 个 "abcde" 和 1 个 "abde"，显然最长长度也是 5。
以剩余字符开头
再用相同的逻辑，依次寻找以 text2 中的剩余字符 b, c, d, e 开头的最长公共子序列（每次都会从头到尾地扫描一遍字符串 text1）。大家可以自己手动画下，这里就不再贴类似逻辑的图了。
代码实现
代码实现，如下：
var longestCommonSubsequence = function (text1, text2) {
let ans = 0;
// 递归：在 text1[pos~End] 里找以 text2[start] 开头的最长公共子序列
const selected = []; // 匹配到的公共子序列（状态空间）
const recur = function (pos, start) {
// 到结尾了，更新答案
if (pos === text1.length || start === text2.length) {
ans = Math.max(ans, selected.length);
return;
}
// 本层逻辑：N叉，取决于匹配到了几个 text2[start] 字符
for (let i = pos; i < text1.length; i++) {
if (text1[i] === text2[start]) {
selected.push(text2[start]);
recur(i + 1, start + 1); // 从i+1开始找, 找第start+1个字符
selected.pop();
}
}
// 继续从pos开始找, 找以 text2[start+1] 开头的
recur(pos, start + 1);
};
// 开始递归，从 0,0 开始
recur(0, 0);
return ans;
};
执行结果：超出时间限制
超时了。大约在预期之内，接下来看看为什么超时以及如何优化。
分析原因
在上面手动寻找最长公共子序列的过程中，我们也能发现有重复的逻辑。
比如当找完以 text2[1]="a" 开头的最长公共子序列之后，再找以 text2[i]="b","c","d","e" 开头的时候，就和第一处 a 的后续逻辑是完全重叠的，因为它匹配到了 text1[0]——即第一个位置。
而在找 text2[0]="x" 时之所以没有和后续逻辑有大量重叠（只和最后的 e 重复了），是因为它匹配到的位置是在 text1 的倒数第二个。
那么该如何优化呢？老规矩，画状态图，因为相互重叠的逻辑理论上是会落到图中的同一个结点上的。
状态图
继续用上面的例子，字符串 text1 = "abcabcdbdxe", text2 = "xabcde"。
结合暴力搜索的分析和解题思路，我们画的状态图如下——带权重的有向无环图。其中，S 表示 Start 开始结点，E 表示 End 结束结点，两个字符串的相同字符间用双向边相连且权重为 1，其余边的权重均为 0。那么求两个字符串的最长公共子序列，就是求从起点 S 到终点 E 的最大权重路径，其中要求路径中“边1”的两个端点不能同时是另一条“边1”的端点。
严格来说，“暴力搜索”应该是对上面这个状态图的完全遍历？
单从状态图来看，似乎不容易直接想到能避免重复计算的方法，那我们就再思考下动态规划的几个原则。
动态规划
动态规划的原则：
-
确定“状态”的原则：寻找变化的信息 （可参考递归的参数） -
确定“代表”的原则：寻找最优化目标 （不关心具体长啥样，只关心最大长度） -
确定“决策”的原则：人工模拟时的递推思路
回想用暴力搜索解决此问题的过程，手动模拟时找到的阶段性的解是 “以 text2[1]=text1[0]="a" 开头的最长公共子序列找到了 7 个”，在代码中递归求解的也是 “在 text1[i~End] 里找以 text2[j] 开头的最长公共子序列，且末尾会继续递归 recur(i, j+1)”。所以，“变化的信息”就是两个字符串的下标 text1[i] 和 text2[j]，即状态。
动态规划的思路是“从小到大的递推”，所以参数的含义大概率不会和递归的原始含义完全一致，但参数的“形”可以借鉴。
之前是将找出的最长公共子序列存储在共享变量 selected[] 数组中，现在我们不关心具体序列的样子，只关心那个最优化的代表——这些最长公共子序列的最大长度 opt[i][j]，即 text1 的前 i 个字符和 text2 的前 j 个字符能组成的最长公共子序列的长度。
因为是“从小到大的递推”，所以
opt[i][j]所代表的集合不是递归中的以text1[i]和text2[j]“开始”的两个字符串的最长公共子序列，而是以它两为“结尾”的两个字符串的最长公共子序列（否则就得倒着推，这里我们选择正着推，因为更直观些）。
至于决策，尚不清楚。那我们就按照已确定的状态和最优化目标，尝试人工模拟下，看能否找到最优化目标之间的递推公式。
求递推公式
结合上面的分析，我们画个二维表格，手动模拟下 opt[i][j] 的求解过程（如下），其中 opt[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符能组成的最长公共子序列的长度。
可以得到递推公式：
-
如果 text1[i] == text2[j]，那么opt[i][j] = opt[i-1][j-1] + 1 -
如果 text1[i] != text2[j]，那么opt[i][j] = max(opt[i][j-1], opt[i-1][j])
动态规划的代码实现，如下：
var longestCommonSubsequence = function(text1, text2) {
const m = text1.length;
const n = text2.length;
// 最优化目标：以 text1[i], text2[j] 结尾的两个字符串，最长公共子序列的长度是 opt[i+1][j+1]
let opt = new Array(m + 1);
for (let i = 0; i <= m; i++) {
opt[i] = new Array(n + 1).fill(0); // 填充0（含边界初始化）
}
// 开始递推
let ans = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
// 若相等时，从对角线来+1
if (text1[i-1] === text2[j-1]) {
opt[i][j] = opt[i-1][j-1] + 1;
// 否则，取最大值(左侧,上侧)
} else {
opt[i][j] = Math.max(opt[i][j-1], opt[i-1][j]);
}
ans = Math.max(ans, opt[i][j]); // 更新答案
}
}
return ans;
};
执行结果：通过
总结
通常情况，在看到“求最长公共子序列”的问题时，都会很自然地想到用动态规划（求最优解的问题）。本文之所以选择先从暴力搜索开始，就是想更进一步探索“为什么会想到用画表格这么巧妙的方式来进行递推”。
其实，最优化目标是可以直接取题目中的。但是“状态”有时候不怎么直观，不论是先从朴素的思路开始，还是直接从画状态图开始，都是想梳理清楚状态的来龙去脉。一旦最优化目标和状态都确定好了，递推公式往往也就呼之欲出了。
动态规划最难的大约就是“得先有个思路”，哪怕是最朴素的那种。
写在最后
从暴力搜索到动态规划的那个“优化过程”，个人感觉文中的思路还有些跳跃不够流畅。如果你有更好/巧妙的方法，诚邀留言/私信讨论。