动态规划dp——LIS(最长上升子序列)、LCS(最长公共子序列)

子序列：在原序列中按照顺序取出的一些元素。可以不是在原序列中连续的
动态规划中比较重要的就是初始值和状态转移方程

LIS:最长上升子序列
问题：给定一个序列an,请你选出一个子序列，满足序列中的每一项都比他的前一项大
解决：定义f(i)表示到达i位置且i在我选择的子序列中的最长上升子序列的长度。此时表示i是子序列的终点
枚举一个j,满足j<i并且aj<ai，那么ai就可以接在aj的后面，构成一个更长的上升子序列，长度为f(j)+1,最大的一个f(j)+1就是f(i)
应该保证每个位置没更新前，f的值为1

for(int i = 1; i <= n; i ++){
　　f[i] = 1;
　　for(int j = 1; j < i; j ++){
　　if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
　　}
}

LCS:最长公共子序列
问题：有两个数字序列，X，Y,求这两个序列的最长公共子序列
解决：定力f(i,j)表示第一个序列的前i个数字，第二个序列的前j个数字，能构成最长公共子序列的长度。这样最后的答案就是f(n,m)
如果xi==yj,则f(i,j)=max(f(i,j),f(i-1,j-1)+1)
如果不相等，则f(i,j)=max(f(i-1,j,f(i,j-1)))

cin>>n>>m;
memset(f,0,sizeof(f));
for(int i = 1; i <= n ;i ++) cin>>a[i];
for(int i = 1; i <= n ;i ++) cin>>b[i];
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]);
　　　　if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
　　}
}
ans =f[n][m];

LIS和LCS之间的联系
最长公共子序列可以转换为最长上升子序列
步骤：
假设有两个序列S1[1~6]={a,b,c,a,b,c}, S2[1~7]={c,a,b,e,d,a,b}
记录S1中每个元素在S2中出现的位置，并且位置是降序排列，则loc(a)={6,2},loc(b)={7,3},loc(c)={1},loc(d)={5}
将S1中的每个元素的位置按S1中的元素的顺序排列成一个序列S3={6,2,7,3,1,6,2,5,1}
再对S3求LIS的到的值就是求LCS的长度答案

写于2020/8/21 22:47

动态规划dp——LIS(最长上升子序列)、LCS(最长公共子序列)

原文：https://www.cnblogs.com/sunjianzhao/p/13543757.html