poj 最长公共子序列 1458 记忆式搜索

#include <iostream>
using namespace std;
#include<cstring>
#define N 1005
char s1[N],s2[N];
int dp[N][N];
int max(int a,int b) {  return a>b ? a:b ;}

int f(int x ,int y)
{
 if(dp[x][y]!=-1) return dp[x][y];
 if(x==0||y==0)    return dp[x][y]=0;
 else if(s1[x-1]!=s2[y-1])  return dp[x][y]=max(f(x-1,y), f(x,y-1));
       else return dp[x][y]=f(x-1,y-1)+1;
}

int main(int argc, char *argv[])
{    int len1,len2;
 while(cin>>s1>>s2)
 {
  len1=strlen(s1);  len2=strlen(s2);
  
  memset(dp,-1,sizeof(dp));
  f(len1,len2);
cout << dp[len1][len2] << endl ;

 }
 return 0;
}

poj 最长公共子序列 1458 记忆式搜索,布布扣,bubuko.com

原文：http://www.cnblogs.com/2014acm/p/3917505.html