传送门
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] = , b[2001] = ; 9 10 int main() 11View Code
上一篇：[luoguP1962] 斐波那契数列（矩阵快速幂）
下一篇：[luoguP2184] 贪婪大陆（树状数组）
DP
