最长公共子序列

const int N = 1010;      // 定义常量N，表示数组的最大大小
int n, m;                // n和m分别表示两个字符串的长度
char a[N], b[N];         // 定义两个字符数组来存储输入的字符串
int f[N][N];             // 定义二维数组f用于动态规划

int main()
{
    scanf("%d%d", &n, &m);         // 输入两个字符串的长度
    scanf("%s%s", a + 1, b + 1);   // 输入两个字符串，注意从下标1开始存储
    
    // 动态规划求解最长公共子序列
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            // 如果当前两个字符不相同，则公共子序列长度不增加
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            
            // 如果当前两个字符相同，则可以在f[i-1][j-1]的基础上加1
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    
    printf("%d\n", f[n][m]);   // 输出最长公共子序列的长度
    return 0;                  // 程序正常结束
}

注意

---

1. 注意从下标1开始存储
2. 双重循环

3. f[i][j] 存储的是子串 a[1…i] 和子串 b[1…j] 的最长公共子序列长度

4. 疑问：为什么失配的时候不写成f[i][j] =f[i-1][j-1]?
   考虑两个字符串：

   • a = “ABCDE”
   • b = “ACE”

   当我们到达i=4, j=2时：

   • a[4]=”D” 和 b[2]=”C” 不匹配
   • f[3][2] = 2 (子序列是”AC”)
   • f[4][1] = 1 (子序列是”A”)

   如果我们使用 f[i][j] = f[i-1][j-1]，那么 f[4][2] = f[3][1] = 1

   但明显这是错的，因为如果我们把b[2]考虑上，那么a[1…4]和b[1…2]这两个子序列就有”AC”这两个公共子序列，即 f[3][2] = 2。

   所以正确的转移应该是 f[4][2] = max(f[3][2], f[4][1]) = max(2, 1) = 2。

举例

---

假设我们有两个字符串：

• a = “ABC” (n = 3)
• b = “AC” (m = 2)

初始状态：

f[0][0]=f[0][1]=f[0][2]=f[1][0]=f[2][0]=f[3][0] = 0

填表过程：

1. i=1, j=1: 比较 a[1]=”A” 和 b[1]=”A”
   • 它们相等，所以 f[1][1] = f[0][0] + 1 = 1
2. i=1, j=2: 比较 a[1]=”A” 和 b[2]=”C”
   • 它们不相等，所以 f[1][2] = max(f[0][2], f[1][1]) = 1
3. i=2, j=1: 比较 a[2]=”B” 和 b[1]=”A”
   • 它们不相等，所以 f[2][1] = max(f[1][1], f[2][0]) = 1
4. i=2, j=2: 比较 a[2]=”B” 和 b[2]=”C”
   • 它们不相等，所以 f[2][2] = max(f[1][2], f[2][1]) = 1
5. i=3, j=1: 比较 a[3]=”C” 和 b[1]=”A”
   • 它们不相等，所以 f[3][1] = max(f[2][1], f[3][0]) = 1
6. i=3, j=2: 比较 a[3]=”C” 和 b[2]=”C”
   • 它们相等，所以 f[3][2] = max(f[3][2], f[2][1] + 1) = max(1, 1+1) = 2

最终得到 f[3][2] = 2，即最长公共子序列的长度为2