动态规划之三——线性DP入门2

3.1 最长公共子序列（LCS）

3.1.1、问题引入

问题描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列（Longest Common Subsequence）的长度

示例：

输入：text1 = "ABCBDAB", text2 = "BDCAB"
输出：4 
解释：最长公共子序列是 "BCAB" 或 "BDAB"

备注

你先想想，如果用暴力递归，你会怎么做？

3.1.2 暴力递归

暴力递归参考

int lcs(string& text1, string& text2, int i, int j) {
    // 基准条件：任意字符串处理完毕
    if (i == 0 || j == 0) return 0;
    
    // 情况1：末尾字符匹配
    if (text1[i-1] == text2[j-1]) {
        return lcs(text1, text2, i-1, j-1) + 1;
    } 
    // 情况2：末尾字符不匹配
    else {
        return max(
            lcs(text1, text2, i-1, j),   // 舍弃text1的末尾字符
            lcs(text1, text2, i, j-1)    // 舍弃text2的末尾字符
        );
    }
}

暴力递归的问题

1. 重复计算：大量子问题被重复计算

   // 示例：计算lcs(2,2)会被多次调用
   lcs(3,3) -> lcs(2,3) -> lcs(2,2)
   lcs(3,3) -> lcs(3,2) -> lcs(2,2)

2. 效率低下：对于长度为20的字符串就需要约2^40 ≈ 1万亿次计算

改进思路（记忆化递归）

vector<vector<int>> memo(1001, vector<int>(1001, -1));

int lcs_memo(string& t1, string& t2, int i, int j) {
    if (i == 0 || j == 0) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    
    if (t1[i-1] == t2[j-1]) {
        return memo[i][j] = lcs_memo(t1, t2, i-1, j-1) + 1;
    } else {
        return memo[i][j] = max(
            lcs_memo(t1, t2, i-1, j),
            lcs_memo(t1, t2, i, j-1)
        );
    }
}

3.1.3 DP 表格推演图

状态定义

定义 dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的 LCS 长度

备注

画表格推演是用动态规划解决问题时常用的分析技巧，务必掌握！

首先画一个空白二维表格

行索引 i 对应 s1（长度 8），列索引 j 对应 s2（长度 6）。
初始状态：第一行和第一列均为 0。

表格结构

	0	1(A)	2(C)	3(D)	4(D)	5(E)	6(F)
0	0	0	0	0	0	0	0
1(A)	0
2(B)	0
3(C)	0
4(D)	0
5(E)	0
6(F)	0
7(G)	0
8(A)	0

---

分步填充过程

1. 填充 i=1（s1的字符 A）

	0	1(A)	2(C)	3(D)	4(D)	5(E)	6(F)
0	0	0	0	0	0	0	0
1(A)	0	1	1	1	1	1	1
2(B)	0
3(C)	0
4(D)	0
5(E)	0
6(F)	0
7(G)	0
8(A)	0

• 逻辑：A 与 s2 各字符依次比较：
  • j=1（A）: 字符匹配 → dp[1][1] = 0+1=1
  • j>1: 字符不匹配 → 继承左侧最大值 1

---

2. 填充 i=2（s1的字符 B）

	0	1(A)	2(C)	3(D)	4(D)	5(E)	6(F)
0	0	0	0	0	0	0	0
1(A)	0	1	1	1	1	1	1
1(B)	0	1	1	1	1	1	1
3(C)	0
4(D)	0
5(E)	0
6(F)	0
7(G)	0
8(A)	0

• 逻辑：B 与 s2 所有字符均不匹配，继承上方或左侧最大值 1。

---

3. 填充 i=3（s1的字符 C）

	0	1(A)	2(C)	3(D)	4(D)	5(E)	6(F)
0	0	0	0	0	0	0	0
1(A)	0	1	1	1	1	1	1
1(B)	0	1	1	1	1	1	1
3(C)	0	1	2	2	2	2	2
4(D)	0
5(E)	0
6(F)	0
7(G)	0
8(A)	0

• 关键点：
  • j=2（C）: 字符匹配 → dp[3][2] = dp[2][1]+1=2
  • j>2: 继承左侧最大值 2

---

4. 填充 i=4（s1的字符 D）

	0	1(A)	2(C)	3(D)	4(D)	5(E)	6(F)
0	0	0	0	0	0	0	0
1(A)	0	1	1	1	1	1	1
1(B)	0	1	1	1	1	1	1
3(C)	0	1	2	2	2	2	2
4(D)	0	1	2	3	3	3	3
5(E)	0
6(F)	0
7(G)	0
8(A)	0

• 关键点：
  • j=3（第一个 D）: 字符匹配 → dp[4][3] = dp[3][2]+1=3
  • j=4（第二个 D）: 字符匹配 → dp[4][4] = dp[3][3]+1=3（注意继承左侧逻辑）

---

5. 填充后续行（E, F, G, A）

最终填充结果如下：

	0	1(A)	2(C)	3(D)	4(D)	5(E)	6(F)
0	0	0	0	0	0	0	0
1(A)	0	1	1	1	1	1	1
2(B)	0	1	1	1	1	1	1
3(C)	0	1	2	2	2	2	2
4(D)	0	1	2	3	3	3	3
5(E)	0	1	2	3	3	4	4
6(F)	0	1	2	3	3	4	5
7(G)	0	1	2	3	3	4	5
8(A)	0	1	2	3	3	4	5

---

3.1.4 动态规划解法

1. 状态定义

定义 dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的 LCS 长度

2. 状态转移方程

• 当 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])

3. 边界条件

• dp[0][j] = 0 (0 ≤ j ≤ n)
• dp[i][0] = 0 (0 ≤ i ≤ m)

3.1.5 C++实现

基础版本（二维DP）

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

空间优化版本（滚动数组）

备注

思考：

如何压缩空间，降为一维dp数组？

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<int> dp(n+1, 0), pre(n+1, 0);

    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(text1[i-1] == text2[j-1]) {
                dp[j] = pre[j-1] + 1;
            } else {
                dp[j] = max(pre[j], dp[j-1]);
            }
        }
        swap(dp, pre);
        fill(dp.begin(), dp.end(), 0);
    }
    return pre[n];
}

要点

1. 通过填表演示理解状态转移过程
2. 重点讲解状态转移方程的推导过程
3. 通过具体例子（如"ABCBDAB"和"BDCAB"）进行填表演示

扩展练习：

1. 【模板】最长公共子序列
2. [HAOI2010] 最长公共子序列

*学习笔记

暂没有学习笔记，快来抢first blood ！