适用题型：
Description：
给定两个序列A,B，其长度分别为N,M，现在要你求出这两个序列中最长的一个公共子序列，并使这个子序列递增。比如数列{1,2,0,4,5}和{1,0,4,5,2}，其最长公共上升子序列就是{1,4,5}，长度为3。
Input：
第一行：一个N；
第二行：N个数，为数列A；
第三行：一个M；
第四行：M个数，为数列B。
Output：
一个数，为最长公共上升子序列的长度。
Sample Input：
5 1 2 0 4 5 5 1 0 4 5 2
Sample Output：
3
主要思路：每次找a[i]==b[j],(i 1-n,j 1-m)然后查找以前的最长的公共上升子序列的长度，更新一下。
最简单的就是设f[i][j]表示以a[i],b[j](这里a[i]==b[j]),结尾的最长公共子序列长度，Ｏ（ｎ^2*m^2）。因为每次得往后找另一对i，j。总共找两对i，j。
这里为了简化可以设f[j]表示以b[j]结尾的最长公共子序列，每次找a[i]==b[j],然后比较f[j]与前面出现的最大的f[k]+1比较。这里还有个问题就是得存k的值，而且得注意每次对应一个a[i],应该是k从0开始，j 是从1开始
二维数组的代码：
#include<iostream>
#include<string.h>
#define maxn 100
using namespace std;
void fun(char *A,int m,char *B,int n,int a[][maxn],int b[][maxn])
{
for(int i=0;i<=m;i++) a[i][0]=0;
for(int i=0;i<=n;i++) a[0][i]=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(A[i-1]==B[j-1])
{
a[i][j]=a[i-1][j-1]+1;
b[i][j]=0;
}
else if(a[i-1][j]>a[i][j-1])
{
a[i][j]=a[i-1][j];
b[i][j]=1; //行增加，为1
}
else
{
a[i][j]=a[i][j-1];
b[i][j]=-1; //列增加，为-1
}
}
}
}
void print(char *A,int m,char *B,int n,int b[][maxn])
{
if(m==0||n==0) return ;
else if(b[m][n]==0)
{
print(A,m-1,B,n-1,b);
cout<<A[m-1];
}
else if(b[m][n]==1)
{
print(A,m-1,B,n,b);
}
else
{
print(A,m,B,n-1,b);
}
}
int main()
{
char A[maxn],B[maxn];
int a[maxn][maxn]; //记录每个状态的最大字串长
int b[maxn][maxn]; //记录前驱
int m,n;
cin>>A>>B;
m=strlen(A),n=strlen(B);
fun(A,m,B,n,a,b);
cout<<a[m][n]<<endl;
print(A,m,B,n,b);
return 0;
}
代码：
#include<cstdio>
#define MAXN 1000
int n,m;
int a[MAXN],b[MAXN],f[MAXN];
//f[j]表示以j结尾最大值
void dp()
{
for(int i=1; i<=n; i++)
{
int k=0;//设置k从0开始，而i,j都是从1开始的，防止第一组相同的数没有被处理
for(int j=1; j<=m; j++)
{
if(a[i]==b[j])
{
if(f[j]<f[k]+1)
f[j]=f[k]+1;
}
if(a[i]>b[j])//下次比较比a[i]小的数的f值，所以每次遇到比a[i]小的数都得更新小比a[i]小的最大f值
{
if(f[j]>f[k])
k=j;
}
}
}
}
int main()
{
memset(f,0,sizeof(f));
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1; i<=m; i++)
scanf("%d",&b[i]);
dp();
int max=-1;
for(int i=1; i<=m; i++)
{
if(max<f[i])
max=f[i];
}
printf("%d\n",max);
return 0;
}