两个字符串的删除操作

怎样从“word1=sea,word2=eat 最少删除步数使相同。”推导出 二维 DP · 删除操作，并证明每次状态变化都不会漏掉答案？

中心结论：LCS 变种:n+m-2*LCS;或删到相等编辑距离。

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

在本站主例中，word1=sea,word2=eat 最少删除步数使相同。

算法最终需要得到或观察：最少删除 2 步。

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

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

1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2. 2状态只维护 dp[i][j] LCS/删除数。
3. 3转移每一步按照 LCS 变种:n+m-2*LCS;或删到相等编辑距离。
4. 4收尾读取 最少删除 2 步。，并复核边界与复杂度。

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

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

从题目数据量级判断，此题一定是 O(n^2) 动态规划题。定义 `dp[i][j]` 表示 `word1[:i]` 与 `word2[:j]` 匹配所删除的最少步数。如果 `word1[:i-1]` 与 `word2[:j-1]` 匹配，那么 `dp[i][j] = dp[i-1][j-1]`。如果 `word1[:i-1]` 与 `word2[:j-1]` 不匹配，那么需要考虑删除一次，所以 `dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j])`。所以动态转移方程是：

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

最终答案存储在 `dp[len(word1)][len(word2)]` 中。

LCS 变种:n+m-2*LCS;或删到相等编辑距离。

执行过程中持续维护：dp[i][j] LCS/删除数。

正确性依赖以下不变量：最终相同⇔保留 LCS,删其余。

面试时可以压缩为：LCS dp 或删除 dp O(mn)。

落到当前题，执行机制可以压缩为：LCS 变种:n+m-2*LCS;或删到相等编辑距离。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入word1=sea,word2=eat 最少删除步数使相同。 因为：LCS 变种:n+m-2*LCS;或删到相等编辑距离。
2. 2dp[1][1]=1 (替换)三种操作取 min。 因为：经典转移。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4dp[2][1]=1 (匹配)三种操作取 min。 因为：经典转移。
5. 5dp[2][3]=3 (替换)三种操作取 min。 因为：经典转移。
6. 6dp[3][2]=1 (匹配)三种操作取 min。 因为：经典转移。
7. 7编辑距离 2返回右下角。 因为：O(mn)。
8. 8收尾与复杂度最少删除 2 步。 因为：时间 O(n) · 空间 O(1)。LCS 变种:n+m-2*LCS;或删到相等编辑距离。

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

func minDistance(word1 string, word2 string) int {
	dp := make([][]int, len(word1)+1)
	for i := 0; i < len(word1)+1; i++ {
		dp[i] = make([]int, len(word2)+1)
	}
	for i := 0; i < len(word1)+1; i++ {
		dp[i][0] = i
	}
	for i := 0; i < len(word2)+1; i++ {
		dp[0][i] = i
	}
	for i := 1; i < len(word1)+1; i++ {
		for j := 1; j < len(word2)+1; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j])
			}
		}
	}
	return dp[len(word1)][len(word2)]
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
    // 1. 主例
    //    输入：mode="edit-distance", a="sea", b="eat"
    //    期望：最少删除 2 步。
    //
    // 2. 失败 / 未命中
    //    检查：与编辑距离相关但只允许删。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC72 编辑距离；LC1143 LCS
}

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

1. 1题意word1=sea,word2=eat 最少删除步数使相同。
2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3. 3优化LCS 变种:n+m-2*LCS;或删到相等编辑距离。
4. 4证明最终相同⇔保留 LCS,删其余。
5. 5复杂度时间 O(n)，空间 O(1)