poj 1458 Common Subsequence

Description

Input

Output

Sample Input

abcfbc         abfcab
programming    contest 
abcd           mnp

Sample Output

4
2
0

LCS经典题目，重要的是推出递推公式，考虑到是否需要重新计算减少空间，直接贴代码

本题wa了两次，第一次是maxn开大了10010，导致超时，第二次开到110,太小，导致wa

ac之后用的是1010

/*
  time:11/24 2014
  poj:1458
  author:cj

  accept
*/


#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;


const int maxn=1010;
char  x[maxn],y[maxn];
int dp[maxn][maxn];
int m,n;
int i,j;
int main(){
    while(scanf("%s",x+1)!=EOF){
        scanf("%s",y+1);
        memset(dp,0,sizeof(dp));
        m=strlen(x+1);
        n=strlen(y+1);


        //dp[0][0]=0;
        /*for(int i=0;i<m;i++){
            dp[i][0]=0;
        }*/
        /*for(int j=0;j<n;j++){
            //cout<<y[j]<<endl;
            printf("%c ",y[j]);
        }


        /*cout<<x[m]<<y[n]<<endl;
        if(x[0]==y[0]){
            dp[0][0]=1;
        }*/
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(x[i]==y[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                    //cout<<dp[i][j]<<endl;
                }
                else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }


            }
        }
        //cout<<x<<"***"<<y<<endl;*/
        //printf("%s m= %d\n",x,m);
        //printf("%s n= %d\n",y,n);
        cout<<dp[m][n]<<endl;


    }
    return 0;
}

poj 1458 Common Subsequence

原文：http://blog.csdn.net/u012315428/article/details/41449121