[算法总结] LCS 最长公共子序列

划分图

集合

第一个序列的 前i个字母 和 第二个 序列的 前j个字母的公共子序列

属性: MAX (求最大值 是可以有重复的 但是 求数量是不能有重复的)

集合的划分:

用a[i] 和 b[j] 表示当前位置的字符

所以f[i][j] 就可以表示为 选a[i]b[j] , 不选a[i]b[j],选a[i]不选b[j],选b[j]不选a[i]

遗留问题:

中间这两个集合的 最大值一定小于f[i-1,j] 或f[i,j-1]所以我们就可以使用这两个f 来表示这两个集合 (也就是这里 重复了)

为什么不写f[i-1][j-1]

因为f[i-1][j-1] 包含在了f[i-1][j] , f[i][j-1]

Code:

#include 
using namespace std;
const int N  =1010;
int n,m;

char a[N],b[N];
int f[N][N];
int main()
{
    cin>>n>>m;
    cin>>a+1>>b+1;
    for(int i=1;i