最长公共子序列问题:
状态转移方程是: dp[i][j]=dp[i-1][j-1]+1 当x[i]=y[j]时;
dp[i][j]=max{dp[i-1][j],dp[i][j-1]} 当x[i]!=y[j]时;
#include<stdio.h>
#include<string.h>
const int MAXLEN=1001; //原来不会的
char x[MAXLEN],y[MAXLEN];
int c[MAXLEN][MAXLEN];
int max(int m,int n)
{
return m>n?m:n;
}
int main()
{
int i,j,l1,l2;
while(scanf("%s%s",x,y)!=EOF)
{
l1=strlen(x);
l2=strlen(y);
memset(c,0,sizeof(c)); //这条指令是置零用的
for(i=0;i<l1;i++)
for(j=0;j<l2;j++)
{
if(x[i]==y[j]) c[i+1][j+1]=c[i][j]+1; //这里出过错的,注意边界
else c[i+1][j+1]=max(c[i+1][j],c[i][j+1]);
}
printf("%d/n",c[l1][l2]);
}
return 0;
}