最长公共子序列

（3）动态规划

#include<stdio.h>
#include<string.h>
int dp[1000][1000];
int max(int a,int b)
{
    return a=a>b?a:b;
}

void prit(int b[][100],char *x,int i,int j)
{
	if(i==0||j==0) return ;
	if(b[i][j]==0){
		prit(b,x,i-1,j-1);
		printf("%c",x[i]);
	}
	else if(b[i][j]==1){
		prit(b,x,i-1,j);
	}
	else prit(b,x,i,j-1);
}
int main()
{
    char s1[1000],s2[1000];
	int b[100][100];
    while(scanf("%s%s",s1+1,s2+1)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        int i=0;
        int j=0;
        for(i=1;s1[i]!=‘\0‘;i++)
		{
			for(j=1;s2[j]!=‘\0‘;j++)
            {
                if(s1[i]==s2[j])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
					b[i][j]=0;
                }
                else if(dp[i-1][j]>dp[i][j-1])
                {
                    dp[i][j]=dp[i-1][j];
					b[i][j]=1;
                }
				else{
					dp[i][j]=dp[i][j-1];
					b[i][j]=-1;
				}
            }
        }
        printf("%d\n",dp[i-1][j-1]);
		prit(b,s1,i-1,j-1);
		printf("\n");
    }
}

最长公共子序列,布布扣,bubuko.com

最长公共子序列

原文：http://blog.csdn.net/cnh294141800/article/details/22763361