动态规划入门-LIS LCS 最长公共字串 --＞表格法进行还原串
愿我们历尽千帆永远不会失去前行的勇气
LIS o(n*n) 最长上升子序列
#include
using namespace std;
int n=9;
int a[101]={0,5,7,1,9,4,6,2,8,3};
int f[101];int main(){int i,j,ans=1;for(int i=1;i<=n;i++) f[i]=1;for(int i=2;i<=n;i++){//从1开始也可以 for(int j=1;ja[j]){f[i]=max(f[i],f[j]+1);}}ans=max(ans,f[i]);}cout< 优化o(n*logn) 二分算法+贪心思路
实际上输出的不是最长上升序列但是数目和最长上升序列相同。
#include
using namespace std;
int n=9;
int a[101]={0,2,5,9,4,6,7,1,7,2};
int f[101];
int len;
int find(int x){//找出第一个大于等于x的值 int ans=n+1;int l=1,r=len;while(l<=r){int mid=l+r>>1;if(a[mid]>=x){ans=mid;r=mid-1;}else l=mid+1;}return ans;}
int main(){int i,j;len=1;f[1]=a[1];for(i=2;i<=n;i++){if(a[i]>f[len]){f[++len]=a[i];}else {j=find(a[i]);f[j]=a[i];}}printf("%d\n",len);return 0;
} 板子题：
P1439 【模板】最长公共子序列
链接：https://www.luogu.com.cn/problem/P1439
题意：
乍一看像是最长公共子序列的题，但是最长公共子序列需要进行o(n*n)的复杂度
将此题转化成LIS map映射一下即可：如 a： 2 3 4 5 1 b：3 2 3 1 5 用abc来标记a数组则原数组为abcde 为一个单调递增的序列，a和b的公共序列也应该是单调递增，换句话说，如果b有cde这么一段，那么这一段就是公共序列。转化成了求这一段有多长的问题，即LIS。
#include#include using namespace std; int a[100001],b[100001],map[100001],f[100001]; int len; int n;int main(){int j,i;cin>>n;for(i=1;i<=n;i++){scanf("%d",&a[i]);map[a[i]]=i;}for( i=1;i<=n;i++){scanf("%d",&b[i]);}len=0;f[0]=0;for( i=1;i<=n;i++){if(map[b[i]]>f[len]){f[++len]=map[b[i]];}else {int ans=n+1;int l=0,r=len;while(l<=r){int mid=l+r>>1;if(f[mid]>=map[b[i]]){ans=mid;r=mid-1;}else l=mid+1;ans=min(map[b[i]],ans);}j=ans;f[j]=map[b[i]];}}printf("%d\n",len);return 0; }
LCS O（n*n）最长公共子序列 还存在空间上进行优化的问题，滚动数组的题（滚动数组待学习）
#include
using namespace std;
char a[200]="ADABBC";
char b[200]="DBDCA";
char f[201][201];
char p[201][201];
int m,n;
void LCS(){int i,j;m=strlen(a);n=strlen(b);for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(a[i-1]==b[j-1]){f[i][j]=f[i-1][j-1]+1;p[i][j]=1;}else if(f[i][j-1]>f[i-1][j]){f[i][j]=f[i][j-1];p[i][j]=2;}else {f[i][j]=f[i-1][j];p[i][j]=3;}}}printf("%d\n",f[m][n]);}
void getLCS(){int i,j,k;char s[200];i=m;j=n;k=f[m][n];while(i>0&&j>0){if(p[i][j]==1){s[k--]=a[i-1];i--;j--;}else if(p[i][j]==2){j--;}else i--;}for(int i=1;i<=f[m][n];i++){printf("%c",s[i]);}}
int main(){LCS();getLCS();} LIS 状态量是 f[i] 是指以a[i]为结尾的最长的LIS，然后用j指针遍历，得到递推式。
LCS 状态量是 f[i][j] 是指a数组长度为i，b数组长度为j的情况下最长的公共子序列，对于下一步的a[i]和b[j]的状态与是否相等进行讨论得到递推式。
最长公共字串 状态量f[i][j]是指以a[i],b[j]结尾的最长公共串，i和j分别遍历即可。
推荐视频：董晓算法的个人空间_哔哩哔哩_Bilibili
对应博客：2022 年 4月 随笔档案 - 董晓 - 博客园
int lcs(char *str1,char *str2){int len1=(int)strlen(str1);int len2=(int)strlen(str2);int dp[len1+1][len2+1];memset(dp,0,sizeof(dp));int maxlen=0;int maxindex=-1;for(int i=1;i<=len1;i++){for(int j=1;j<=len2;j++){dp[i][j]=(str1[i-1]==str2[j-1])?(dp[i-1][j-1]+1):0;if(dp[i][j]>maxlen){maxlen=dp[i][j];maxindex=j-1;}}}for(int k=maxindex-maxlen+1;k<=maxindex;k++){printf("%c",str2[k]);}printf("\n");return maxlen;
} //最长公共字串本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！