描述:
寻找两个字符串中的最长相同序列,不一定连续。
思路:
利用Dp,状态转移方程
1.C[i+1][j+1]+1 (X[i]=Y[j])
C[i][j] = 2.Max(C[i+1][j],C[i][j+1]) (X[i]!=Y[j])
相对来说是简单的dp入门题目。
实现代码:
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define N 10010
char X[N],Y[N];
int C[N][N];
void Solve(int m,int n)
{
int i,j;
for(i=0;i<=m;i++)
{
C[i][n]=0;
}
for(j=0;j<=n;j++)
{
C[m][j]=0;
}
for(i=m-1;i>=0;i--)
{
for(j=n-1;j>=0;j--)
{
if(X[i]==Y[j])
{
C[i][j]=C[i+1][j+1]+1;
}
else
{
if(C[i+1][j]>C[i][j+1])
{
C[i][j]=C[i+1][j];
}
else
{
C[i][j]=C[i][j+1];
}
}
}
}
}
int main()
{
while(scanf("%s%s",X,Y)==2)
{
int m=strlen(X);
int n=strlen(Y);
Solve(m,n);
printf("%d\n",C[0][0]);
}
return 0;
}
--转自