最长公共子序列

怎样从“text1=abcde,text2=ace , LCS 长度 3(ace)。”推导出 二维 DP · LCS，并证明每次状态变化都不会漏掉答案？

中心结论：dp[i][j]=字符同则 1+dp[i-1][j-1] else max(上,左)。

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

在本站主例中，text1=abcde,text2=ace , LCS 长度 3(ace)。

算法最终需要得到或观察：LCS=3。

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2. 2状态只维护 dp 表 i/j。
3. 3转移每一步按照 dp[i][j]=字符同则 1+dp[i-1][j-1] else max(上,左)。
4. 4收尾读取 LCS=3。，并复核边界与复杂度。

先写清 dp 状态含义，再推导转移、初值和遍历顺序。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：dp 表 i/j。

这一题是经典的最长公共子序列的问题。解题思路是二维动态规划。假设字符串 `text1` 和 `text2` 的长度分别为 `m` 和 `n`，创建 `m+1` 行 `n+1` 列的二维数组 `dp`，定义 `dp[i][j]` 表示长度为 i 的 `text1[0:i-1]` 和长度为 j 的 `text2[0:j-1]` 的最长公共子序列的长度。先考虑边界条件。当 `i = 0` 时，`text1[]` 为空字符串，它与任何字符串的最长公共子序列的长度都是 `0`，所以 `dp[0][j] = 0`。同理当 `j = 0` 时，`text2[]` 为空字符串，它与任何字符串的最长公共子序列的长度都是 `0`，所以 `dp[i][0] = 0`。由于二维数组的大小特意增加了 `1`，即 `m+1` 和 `n+1`，并且默认值是 `0`，所以不需要再初始化赋值了。 当 `text1[i−1] = text2[j−1]` 时，将这两个相同的字符称为公共字符，考虑 `text1[0:i−1]` 和 `text2[0:j−1]` 的最长公共子序列，再增加一个字符（即公共字符）即可得到 `text1[0:i]` 和 `text2[0:j]` 的最长公共子序列，所以 `dp[i][j]=dp[i−1][j−1]+1`。当 `text1[i−1] != text2[j−1]` 时，最长公共子序列一定在 `text[0:i-1], text2[0:j]` 和 `text[0:i], text2[0:j-1]` 中取得。即 `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`。所以状态转移方程如下：

$$dp[i][j] = \left\{\begin{matrix}dp[i-1][j-1]+1 &,text1[i-1]=text2[j-1]\\max(dp[i-1][j],dp[i][j-1])&,text1[i-1]\neq text2[j-1]\end{matrix}\right.$$

最终结果存储在 `dp[len(text1)][len(text2)]` 中。时间复杂度 `O(mn)`，空间复杂度 `O(mn)`，其中 `m` 和 `n` 分别是 `text1` 和 `text2` 的长度。

dp[i][j]=字符同则 1+dp[i-1][j-1] else max(上,左)。

执行过程中持续维护：dp 表 i/j。

正确性依赖以下不变量：dp 表示前缀 LCS 长度。

面试时可以压缩为：二维 DP，时间 O(mn) 空间 O(mn)。

落到当前题，执行机制可以压缩为：dp[i][j]=字符同则 1+dp[i-1][j-1] else max(上,左)。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入text1=abcde,text2=ace , LCS 长度 3(ace)。 因为：dp[i][j]=字符同则 1+dp[i-1][j-1] else max(上,左)。
2. 2'a' 匹配,dp=1状态转移。 因为：匹配则 +1,否则 max 上左。
3. 3不匹配,取 max(上,左)=1状态转移。 因为：匹配则 +1,否则 max 上左。
4. 4不匹配,取 max(上,左)=1状态转移。 因为：匹配则 +1,否则 max 上左。
5. 5不匹配,取 max(上,左)=1状态转移。 因为：匹配则 +1,否则 max 上左。
6. 6不匹配,取 max(上,左)=1状态转移。 因为：匹配则 +1,否则 max 上左。
7. 7'c' 匹配,dp=2状态转移。 因为：匹配则 +1,否则 max 上左。
8. 8收尾与复杂度LCS=3。 因为：时间 O(mn) · 空间 O(mn)。dp[i][j]=字符同则 1+dp[i-1][j-1] else max(上,左)。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func longestCommonSubsequence(text1 string, text2 string) int {
	if len(text1) == 0 || len(text2) == 0 {
		return 0
	}
	dp := make([][]int, len(text1)+1)
	for i := range dp {
		dp[i] = make([]int, len(text2)+1)
	}
	for i := 1; i < len(text1)+1; i++ {
		for j := 1; j < len(text2)+1; j++ {
			if text1[i-1] == text2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i][j-1], dp[i-1][j])
			}
		}
	}
	return dp[len(text1)][len(text2)]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
    // 1. 主例
    //    输入：mode="lcs", a="abcde", b="ace"
    //    期望：LCS=3。
    //
    // 2. 失败 / 未命中
    //    检查：滚动数组可把空间降到 O(min(m, n))。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC72 编辑距离；LC583 删除
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意text1=abcde,text2=ace , LCS 长度 3(ace)。
2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3. 3优化dp[i][j]=字符同则 1+dp[i-1][j-1] else max(上,左)。
4. 4证明dp 表示前缀 LCS 长度。
5. 5复杂度时间 O(mn)，空间 O(mn)