f[i][j] 表示第 1 个串匹配到第 i 位，第 2 个串匹配到第 j 位的答案。
f[i][j] = max(f[i - 1][j], f[i][j - 1]) (a[i] != b[j])
f[i][j] = max(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] + 1) (a[i] == b[j])
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 using std::max; 6 7 int n, m, f[2001][2001]; 8 char a[2001] = {'0'}, b[2001] = {'0'}; 9 10 int main() 11 { 12 int i, j; 13 scanf("%s %s", a + 1, b + 1); 14 n = strlen(a); 15 m = strlen(b); 16 for(i = 1; i < n; i++) 17 for(j = 1; j < m; j++) 18 if(a[i] == b[j]) f[i][j] = max(f[i - 1][j - 1] + 1, max(f[i - 1][j], f[i][j - 1])); 19 else f[i][j] = max(f[i - 1][j], f[i][j - 1]); 20 printf("%d", f[n - 1][m - 1]); 21 return 0; 22 }