子序列：在原序列中按照顺序取出的一些元素。可以不是在原序列中连续的
动态规划中比较重要的就是初始值和状态转移方程
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); } }
这样求最长上升子序列是非常容易编写并且易于理解的，但是这样的复杂度比较高O(n^2),在很多情况下都是不能被接受的
所以在竞赛过程中一般使用的是nlgn的算法复杂度，而最长上升子序列也有这样的算法。
算法： 同样定义一个数组f不过含义与原先的不一样，f[i]表示长度为i的子序列终点元素的最小值。这是因为对于当前元素，要想加入到一个子序列中使得原先子序列的长度加1，变为i+1,那么这个时候只需要找到长度为i的子序列的结尾的最小元素（长度为i的子序列可能会有很多组，但是只需要考虑这些组中结尾元素最小的就可以额可）就可以。那么显而易见的是f数组的元素是一个单调递增的序列。可以使用反证发来理解，当f[i+1]<=f[i],那么序列长度为i+1的的序列的第i个数必然<f[i+1],那么也一定<f[i],那么一个i个长度子序列再加上f[i]这个数值肯定是i+1长度的，所以可以知道这种情形是不存在的。那么接下来遍历每一个原序列的元素就可以二分数组f，找到其中恰好大于当前元素的位置，这个时候，f中的这个位置就可以变为当前遍历的原序列的元素。那么最后f中最后一个非0元素的位置就是最长上升子序列的长度。
int make(int cnt,int c[]){//cnt是序列c的长度 if(cnt==0) return 0; memset(f,0,sizeof(f)); int len=1; f[1]=c[0]; for(int i=1;i<cnt;i++){ if(c[i]>f[len]){ f[++len]=c[i]; } else { int l=1,r=len; while(l<r){ int mid=(l+r)>>1; if(f[mid]<c[i]) l=mid+1; else r=mid; } f[l]=c[i]; } } for(int i=cnt;i;i--){ if(f[i]>0) return i; } }
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
修改于202/8/22 16:26