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

时间:2014-08-17 11:37:42   收藏:0   阅读:356

bubuko.com,布布扣

#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

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!