最长公共子序列的变种：两个字符串的删除操作

题目描述
给定两个单词 word1 和 word2，每次操作可以删除任意一个字符串中的一个字符。请计算使得 word1 和 word2 相同所需的最小删除操作次数。

示例
输入：word1 = "sea", word2 = "eat"
输出：2
解释：第一步删除 word1 的 's'，变成 "ea"；第二步删除 word2 的 't'，变成 "ea"。最终两个字符串相同，总删除次数为 2。

解题思路

1. 问题转化
   最小删除次数等价于保留两个字符串的最长公共子序列（LCS），其余字符全部删除。
   因此，最小删除次数 = len(word1) + len(word2) - 2 * len(LCS)。

2. 动态规划定义
   设 dp[i][j] 表示 word1 的前 i 个字符和 word2 的前 j 个字符的 LCS 长度。
   初始状态：dp[0][j] = 0 和 dp[i][0] = 0（空字符串的 LCS 长度为 0）。

3. 状态转移方程

   • 若 word1[i-1] == word2[j-1]：当前字符匹配，LCS 长度加 1。
     dp[i][j] = dp[i-1][j-1] + 1
   • 若字符不匹配：继承左侧或上方的较大值（即忽略当前不匹配的字符）。
     dp[i][j] = max(dp[i-1][j], dp[i][j-1])

4. 计算最小删除次数
   最终 LCS 长度保存在 dp[m][n]，其中 m = len(word1), n = len(word2)。
   最小删除次数 = m + n - 2 * dp[m][n]。

逐步推导示例
以 word1 = "sea", word2 = "eat" 为例：

1. 初始化 dp 表（大小为 4×4，因字符串长度均为 3）：

       ""  e  a  t
    ""  0  0  0  0
    s   0  ?  ?  ?
    e   0  ?  ?  ?
    a   0  ?  ?  ?
   

2. 填充表格：

   • (s, e) 不匹配：dp[1][1] = max(0, 0) = 0
   • (s, a) 不匹配：dp[1][2] = max(0, 0) = 0
   • (s, t) 不匹配：dp[1][3] = 0
   • (e, e) 匹配：dp[2][1] = dp[1][0] + 1 = 1
   • (e, a) 不匹配：dp[2][2] = max(dp[1][2]=0, dp[2][1]=1) = 1
   • (e, t) 不匹配：dp[2][3] = max(dp[1][3]=0, dp[2][2]=1) = 1
   • (a, e) 不匹配：dp[3][1] = max(dp[2][1]=1, dp[3][0]=0) = 1
   • (a, a) 匹配：dp[3][2] = dp[2][1] + 1 = 2
   • (a, t) 不匹配：dp[3][3] = max(dp[2][3]=1, dp[3][2]=2) = 2
     最终 dp[3][3] = 2（LCS 为 "ea"）。

3. 计算删除次数：3 + 3 - 2 * 2 = 2。

关键点

• 本题本质是 LCS 的变形，通过动态规划避免暴力枚举所有子序列。
• 时间复杂度 O(mn)，空间复杂度可优化至 O(min(m,n))。