第一部分 最长上升子序列，最长上升子串，最长公共子序列，最长公共子串--dp
第二部分 KMP，trie，双指针
第三部分 待定
动态规划：审题，状态确定，状态转移，边界条件
线性DP
最长上升子序列
403 线性DP 最长上升子序列【动态规划】_哔哩哔哩_bilibili
给定一个无序整数数组，找出其中最长上升子序列（LIS）的长度。
输入：【5，7，1，9，4，6，2，8，3】
输出：4
解释：最长上升子序列是【1，4，6，8】，其长度是4
如何思考解决这个问题，用s表示这个数组，设f(i)表示以s[i]结尾的的最长上升子序列长度，边界条件f(0)=1,思考当i>=1时，f(i)与f(i-1)的关系，考虑s[i]和s[i-1]，或者考虑s[i]与s[0]...s[i-1]，至少有一点，f(i)大于等于f(i-1),遍历s[0]...s[i-1]，如果记录最大的j，使得s[j]<s[i],且j尽可能大，f(i)=max(f(i-1),f(j)+1)，该递推式有问题，修正，f(i)=max(f(i),f(j)+1)，这样就没有问题了，
比如5，7，1，9，4，6，2，8，3
f(0)=1,f(1)=2,f(2)=1,f(3)=f(2)+1=3,f(4)=2,f(5)=3,f(6)=2,f(7)=4,f(8)=3
上述的过程是可行的，记录最大的f(i)即可，就是答案，如果f(i)表示以s[i]结尾的子串的最长上升子序列，那么显然有f(i)大于f(i-1)，但是难以列出状态转移方程。
另外，设f(i)表示以s[i]开头的最长上升子序列长度，从后往前遍历，对于5，7，1，9，4，6，2，8，3 这列数，一共9个数，数组下标从0开始，初始条件f(8)=1，当s[i]<s[i+1]时，更新f(i)=max(f(i),f(i+1)+1)，
最长上升序列求解，重点在于如何将状态函数与字符串之间的关系唯一确定下来，如果采用以s[i]结尾的最长公共子序列长度作为f(i)的含义，从前往后搜索，可以得到转换公式；如果采用以s[i]开头的最长公共子序列长度作为f(i)的含义，改变搜索方向，同样可以得到转换的公式。如果采用s[0]...s[i]的最大上升子序列长度作为f(i)的含义，很难得到转换公式，f(i)的值（但是这个是根据题目含义最容易想的状态含义，难以求解出状态转移方程）
如何确定状态函数的含义
定义f(i)表示爬到高度为i时需要的期望时间，由高度i-1可以转换为两个状态，分别是高度0，概率是pi；转换为高度i,概率是1-pi；在上述定义下，难以写出转换方程
定义f(i)为从高度为i爬到树顶需要的期望时间，则f(树高度)=0,状态转移是，f(i-1)=(1-pi)*f(i)+pi*f(0)+1，需要求解的就是从树的底部（高度为0）爬到树顶经过的时间的期望值f(0).
最长公共子序列
给定两个字符串，输出其最长公共子序列的长度，输入，ADABEC与DBDCA
输出：3
解释：最长公共子序列是DBC，长度是3
从左向右扫描两个字符串a,b，指针分别使用i和j，状态变量，看作自变量i和j的函数，数据结构实现可以使用二维数组，f(i,j)表示a[0]...a[i]与b[0]...b[j]的最长公共子序列长度，f(0,0)=0,状态转移方程，如果a[i]=b[j]，有f(i,j)=f(i-1,j-1)+1，如果a[i]!=b[j]，分为三种情况，分别是a[i]不在最长公共子序列中，f(i,j)=f(i-1,j),b[j]不在最长公共子序列中，f(i,j)=f(i,j-1),a[i]和b[j]都不在最长公共子序列中，f(i,j)=f(i-1,j-1),其中第三种可以看成前两种的特例，如果a[i]!=b[j]有f(i,j)=max(f(i-1,j),f(i,j-1));
最长上升子串
参考最长上升子序列做法，设f(i)表示以s[i]结尾的最长上升子串的长度，f(0)=0，如果s[i]>s[i-1],f(i)=f(i-1)+1,否则f(i)=0;最长上升子串长度是最大的f(j),j=0,1,...,n-1.
最长公共子串
参考最长公共子序列做法，设f(i,j)表示a[0]...a[i]和b[0]...b[j]的最长公共子串的长度，f(0,0)=0，如果a[i]!=b[j],f(i,j)=0;如果a[i]==b[j]，则f(i,j)=f(i-1,j-1)+1;
只有当两个字符串中的字符连续相等时，公共字串的长度才不断增加。
最长上升公共子串
参考最长公共子序列做法，设f(i,j)表示a[0]...a[i]和b[0]...b[j]的最长公共子串的长度，f(0,0)=0，如果a[i]!=b[j],f(i,j)=0;如果a[i]>a[i-1]且b[j]>b[j-1]且a[i]==b[j]且a[i-1]==b[j-1]，则f(i,j)=f(i-1,j-1)+1;如果a[i]==b[j]且a[i-1]==b[j-1]且a[i]>a[i-1]，则f(i,j)=f(i-1,j-1)+1;否则，如果a[i]==b[j]，则f(i,j)=1;，否则f(i,j)=0.
最长上升公共子序列
上面已经了解到最长上升子序列和最长公共子序列的求解，状态定义和状态转移方程，此处可以将二者结合
最长上升子序列的状态f(i)定义为以s[i]结尾的最长上升子串长度，当s[i]>s[i-1]时，f(i)=f(i-1)+1；当s[i]<=s[i-1]时，遍历s[0]...s[i-1]，如果s[j]<s[i-1]，则f(i)=max(f(i),f(j)+1)，f(0)=0，结果是最大的
最长公共子串的状态定义为f(i,j)表示a[0]...a[i]和b[0]...b[j]的最长公共子串长度，初始f(0,0)=0,如果a[i]==b[j],f(i,j)=f(i-1,j-1)+1;否则，f(i,j)=0;
从上面两个可以看出，最长上升子序列长度求解复杂一些，
对于最长上升公共子序列长度求解，定义f(i,j)表示以a[i]和b[j]结尾的最长公共上升子序列长度，f(0,0)=0,如果a[i]!=b[j]，f(i,j)=0;；如果a[i]==b[j],寻找最长上升公共子序列长度，待续******
对于最长上升公共子序列长度求解，定义f(i,j)表示以a[i]和b[j]结尾的最长公共上升子序列长度，f(0,0)=0,如果a[i]!=b[j]，f(i,j)=0;；
如果a[i]==b[j],寻找最长上升公共子序列长度，参考最长上升子序列的求解，遍历ii=0,...i-1,jj=0,...,j-1,如果a[ii]<a[i]且b[jj]<b[j]且a[ii]==b[jj]，则f(i,j)=max(f(i,j),f(ii,jj)+1);；
简化一下，遍历ii=0,...i-1,jj=0,...,j-1,如果a[ii]==b[jj]且a[ii]<a[i]，则f(i,j)=max(f(i,j),f(ii,jj)+1);；
最后，输出最大的f(i,j)就是所求答案。时间复杂度是O(n^4)
#include<bits/stdc++.h>
using namespace std;
const int N=100;
//LICS
//lis,lcs
char a[N],b[N];
int f[N][N];
int max_len=-1;
void work(){
if(a[0]==b[0])f[0][0]=1;else f[0][0]=0;
for(int i =0 ;a[i];i++)
for(int j = 0;b[j];j++)
if(a[i]!=b[j]){
f[i][j]=0;
}else {
f[i][j]=1;
for(int ii=0;ii<i;ii++)
for(int jj=0;jj<j;jj++)
if(a[ii]==b[jj]&&a[ii]<a[i])
f[i][j]=max(f[i][j],f[ii][jj]+1);
max_len=max(max_len,f[i][j]);
}
for(int i =0 ;a[i];i++)
for(int j = 0;b[j];j++)
cout<<i<<" "<<j<<f[i][j]<<"\t";
cout<<max_len<<endl;
}
int main(){
int n;
cin>>n;
for(int i = 0;i < n;i++)cin>>a[i];
for(int i = 0;i < n;i++)cin>>b[i];
work();
return 0;
}
7
7 1 5 6 4 2 7
7 1 5 4 6 7 2
上述复杂度高的原因：对于最长上升公共子序列长度求解，定义f(i,j)表示以a[i]和b[j]结尾的最长公共上升子序列长度，f(0,0)=0,如果a[i]!=b[j]，f(i,j)=0;；对于结尾元素的限制有两个，一个是字符串a，另一个是字符串b，限制了最后的1结尾的元素。
定义f(i,j)表示以a[i]和b[j]结尾的最长公共上升子序列长度，事实上，任意一个字符串只能有一个结尾，任选限制条件为a[i]或者b[j]结尾即可。
如果只限制一个结尾元素，定义f(i,j)表示以a[0]...a[i]和b[0]...b[j]的最长公共上升子序列长度，限制该最长公共子序列是以a[i]结尾的（不限制不一定要以b[i[结尾）。这样，如果a[i]!=b[jj],jj=0,...,j,那么f[i][j]=0;否则，f[i][j]至少取值为1
遍历jj=0,...,j，当a[i]==b[jj]且 ***************
AcWing 272. 最长公共上升子序列 - AcWing
O(n^3)文章来源：https://www.toymoban.com/news/detail-470861.html
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=3010;
int n;
int a[N],b[N];
int f[N][N];
int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++)scanf("%d",&a[i]);
for(int i = 1;i <=n;i++)scanf("%d",&b[i]);
for(int i = 1;i <=n;i++)
for(int j = 1; j<= n;j++)
{
f[i][j]=f[i-1][j];
if(a[i]==b[j]){
int maxv=1;
for(int k = 1;k< j;k++)
if(b[k]<b[j])maxv=max(maxv,f[i-1][k]+1);
f[i][j]=max(maxv,f[i][j]);
}
}
int res=0;
for(int i = 1;i <= n;i++)res=max(res,f[n][i]);
printf("%d\n",res);
return 0;
}O(n^2)文章来源地址https://www.toymoban.com/news/detail-470861.html
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=3010;
int n;
int a[N],b[N];
int f[N][N];
int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++)scanf("%d",&a[i]);
for(int i = 1;i <=n;i++)scanf("%d",&b[i]);
for(int i = 1;i <=n;i++){
int maxv=1;
for(int j = 1; j<= n;j++)
{
f[i][j]=f[i-1][j];
if(a[i]==b[j])
f[i][j]=max(maxv,f[i][j]);//使用记录的最大值
if(b[j]<a[i])maxv=max(maxv,f[i-1][j]+1) ;
}
}
int res=0;
for(int i = 1;i <= n;i++)res=max(res,f[n][i]);
printf("%d\n",res);
return 0;
}到了这里，关于字符串---第一部分 序列、字串；上升，公共的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
