线性DP习题

字符串 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] 就表示两个前缀之间的答案。