字符串 DP：LCS 与编辑距离

一、1143 最长公共子序列 LCS
1. 前提条件

给两个字符串：

char* text1;
char* text2;

要求：最长公共子序列长度

注意：子序列可以不连续，但顺序不能变。

例如：

text1 = "abcde"
text2 = "ace"

答案是：3
因为公共子序列是："ace"

2. 二维 DP 回顾
状态定义：
dp[i][j]

表示：

text1 前 i 个字符和text2 前 j 个字符的最长公共子序列长度。

转移：

如果 text1[i-1] == text2[j-1]：

    dp[i][j] = dp[i-1][j-1] + 1

否则：

    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

二、LCS 简化成一维数组
1. 为什么能压缩？

二维转移里：

dp[i][j]

只依赖三个位置：

dp[i-1][j]      上方
dp[i][j-1]      左方
dp[i-1][j-1]    左上角

所以我们可以用一维数组：dp[j]

表示：
当前处理到 text1 的某一行时，
text2 前 j 个字符的 LCS 长度。

2. 一维 DP 的关键变量

压缩后：dp[j]

在更新前表示：上一行的 dp[i-1][j]

更新后表示：当前行的 dp[i][j]

但是我们还需要：

左上角 dp[i-1][j-1]

所以用一个变量保存：

int pre;

pre 表示：

上一行左上角的值 dp[i-1][j-1]

3. LCS 一维 DP 代码
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int longestCommonSubsequence(char* text1, char* text2) {
    int m = strlen(text1);
    int n = strlen(text2);

    int* dp = malloc((n + 1) * sizeof(int));

    for (int j = 0; j <= n; j++) {
        dp[j] = 0;
    }

    for (int i = 1; i <= m; i++) {
        int pre = 0;

        for (int j = 1; j <= n; j++) {
            int temp = dp[j];

            if (text1[i - 1] == text2[j - 1]) {
                dp[j] = pre + 1;
            } else {
                dp[j] = max(dp[j], dp[j - 1]);
            }
//相当于pre用的是上一次被覆盖前的值，需要保留下来
            pre = temp;
        }
    }

    int ans = dp[n];

    free(dp);

    return ans;
}

4. 这几个变量怎么理解？
int temp = dp[j];

保存的是：还没更新前的 dp[j]
也就是上一行的 dp[i-1][j]

pre
保存的是：

上一行左上角 dp[i-1][j-1]
dp[j - 1]

因为当前行从左到右更新，所以它表示：

当前行左边 dp[i][j-1]

所以：

dp[j]     更新前：dp[i-1][j]
dp[j-1]   已更新：dp[i][j-1]
pre       左上角：dp[i-1][j-1]

三、LCS 一维例题
text1 = "abc"
text2 = "ac"

答案应该是：2

公共子序列："ac"
初始
text2 = ""  a  c
dp    =  0  0  0
i = 1，text1[i-1] = 'a'

初始：

pre = 0
j = 1，text2[j-1] = 'a'

相等：

dp[1] = pre + 1 = 1

更新后：

dp = [0, 1, 0]
j = 2，text2[j-1] = 'c'

不等：

dp[2] = max(dp[2], dp[1]) = max(0,1) = 1

更新后：

dp = [0, 1, 1]
i = 2，text1[i-1] = 'b'

和 a、c 都不等。

最终：

dp = [0, 1, 1]
i = 3，text1[i-1] = 'c'
j = 1，text2[j-1] = 'a'

不等：
dp[1] = max(dp[1], dp[0]) = 1
j = 2，text2[j-1] = 'c'

相等：dp[2] = pre + 1

这里 pre 是上一行左上角：

dp[i-1][j-1] = dp[2][1] = 1

所以：dp[2] = 2

最终：

dp = [0, 1, 2]

答案：dp[2] = 2

四、72 编辑距离
1. 前提条件

给两个字符串：

char* word1;
char* word2;

可以对 word1 做三种操作：

插入一个字符
删除一个字符
替换一个字符

要求：把 word1 变成 word2 的最少操作次数。

五、编辑距离递归思路
1. 递归定义

定义：

dfs(i, j)

表示：

把 word1 前 i 个字符
变成 word2 前 j 个字符

最少需要多少次操作。
2. 当前字符相等

如果：word1[i - 1] == word2[j - 1]

最后一个字符已经一样，不需要操作：

dfs(i, j) = dfs(i - 1, j - 1)
3. 当前字符不相等

如果：

word1[i - 1] != word2[j - 1]

有三种操作。

操作一：删除

删除 word1[i-1]：

dfs(i - 1, j) + 1
操作二：插入

在 word1 后面插入 word2[j-1]：

dfs(i, j - 1) + 1

为什么是 dfs(i, j-1)？

因为插入后，word2[j-1] 已经匹配掉了，接下来只需要把：

word1 前 i 个字符
变成
word2 前 j-1 个字符
操作三：替换

把 word1[i-1] 替换成 word2[j-1]：

dfs(i - 1, j - 1) + 1
4. 递归转移
如果 word1[i-1] == word2[j-1]：

    dfs(i,j) = dfs(i-1,j-1)

否则：

    dfs(i,j) =
    min(
        dfs(i-1,j),
        dfs(i,j-1),
        dfs(i-1,j-1)
    ) + 1
六、编辑距离 DP 数组
1. DP 定义
dp[i][j]

表示：

把 word1 前 i 个字符
变成 word2 前 j 个字符

的最少操作次数。
2. 初始化
dp[0][j] = j

意思是：

word1 是空串，
要变成 word2 前 j 个字符，
只能插入 j 次。
dp[i][0] = i

意思是：

word2 是空串，
word1 前 i 个字符要变成空串，
只能删除 i 次。
3. DP 转移
如果 word1[i-1] == word2[j-1]：

    dp[i][j] = dp[i-1][j-1]

否则：

    dp[i][j] =
    min(
        dp[i-1][j],      删除
        dp[i][j-1],      插入
        dp[i-1][j-1]     替换
    ) + 1
4. 编辑距离 C 代码
#include <stdlib.h>
#include <string.h>

int min3(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int minDistance(char* word1, char* word2) {
    int m = strlen(word1);
    int n = strlen(word2);

    int** dp = malloc((m + 1) * sizeof(int*));

    for (int i = 0; i <= m; i++) {
        dp[i] = malloc((n + 1) * sizeof(int));
    }

    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }

    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min3(
                    dp[i - 1][j],
                    dp[i][j - 1],
                    dp[i - 1][j - 1]
                ) + 1;
            }
        }
    }

    int ans = dp[m][n];

    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }

    free(dp);

    return ans;
}
七、编辑距离例题
word1 = "horse"
word2 = "ros"

答案是：

3

一种操作：

horse -> rorse    替换 h 为 r
rorse -> rose     删除 r
rose  -> ros      删除 e
DP 表含义

行是 word1 前 i 个字符：

"" h o r s e

列是 word2 前 j 个字符：

"" r o s

最终求：

dp[5][3]

也就是：

horse -> ros
初始化
      ""  r  o  s
""     0  1  2  3
h      1
o      2
r      3
s      4
e      5
填表规则

如果字符相等：

直接看左上角

如果字符不等：

从 上、左、左上 三个位置取最小，再 +1

最终表：

      ""  r  o  s
""     0  1  2  3
h      1  1  2  3
o      2  2  1  2
r      3  2  2  2
s      4  3  3  2
e      5  4  4  3

答案：

dp[5][3] = 3
八、LCS 和编辑距离对比
题目	dp[i][j] 含义	相等时	不等时
LCS	两个前缀的最长公共子序列长度	dp[i-1][j-1]+1	max(dp[i-1][j], dp[i][j-1])
编辑距离	word1 前 i 个变 word2 前 j 个的最少操作数	dp[i-1][j-1]	min(上, 左, 左上)+1
九、易错点
1. dp[i][j] 对应的是前 i 个字符

所以访问字符串时：

word1[i - 1]
word2[j - 1]
2. LCS 是求最大长度

所以用：

max(...)
3. 编辑距离是求最小操作次数

所以用：

min(...)
4. 编辑距离初始化很重要
dp[0][j] = j
dp[i][0] = i

因为空串变非空串只能插入，非空串变空串只能删除。

十、总结
字符串 DP 总结

--------------------------------
1143 最长公共子序列
--------------------------------

dp[i][j]：

text1 前 i 个字符
和 text2 前 j 个字符
的最长公共子序列长度。

如果 text1[i-1] == text2[j-1]：

    dp[i][j] = dp[i-1][j-1] + 1

否则：

    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

一维优化：

dp[j] 表示当前行的 dp[i][j]

pre 表示左上角 dp[i-1][j-1]

temp 保存更新前的 dp[j]

--------------------------------
72 编辑距离
--------------------------------

dp[i][j]：

word1 前 i 个字符
变成 word2 前 j 个字符
的最少操作数。

如果 word1[i-1] == word2[j-1]：

    dp[i][j] = dp[i-1][j-1]

否则：

    dp[i][j] =
    min(
        dp[i-1][j],      删除
        dp[i][j-1],      插入
        dp[i-1][j-1]     替换
    ) + 1

初始化：

dp[0][j] = j
dp[i][0] = i

字符串 DP 通常是在比较两个前缀，dp[i][j] 就表示两个前缀之间的答案。