hdu 1059 Common Subsequence动态规划

                                   f(i-1,j-1)+1 (a[i]==b[j])

f(i,j)= {

                                 max(f(i-1,j),f(i,j-1)) (a[i]!=b[j]) 

#include<stdio.h>
#include<string.h>
int dp[1000][1000];
int max(int a,int b)
{
    return a=a>b?a:b;
}
int main()
{
    char s1[1000],s2[1000];
    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;
                }
                else
                {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        printf("%d\n",dp[i-1][j-1]);
    }
}

hdu 1059 Common Subsequence动态规划

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