POJ 1458 Common Subsequence - Vontroy

#include <iostream>

#include <cstdio>

#include <string>

using namespace std;

const int maxn = 301;

string str1, str2;

int main()

{

while( cin >> str1 >> str2 )

{

int dp[maxn][maxn] = {0};

int len1 = str1.length();

int len2 = str2.length();

for( int i = 1; i <= len1; i++ )

for( int j = 1; j <= len2; j++ )

{

if( str1[i - 1] == str2[j - 1] )

dp[i][j] = dp[i - 1][j - 1] + 1;

else

dp[i][j] = max( dp[i][j - 1], dp[i - 1][j] );

}

printf("%d\n", dp[len1][len2]);

}

return 0;

}

posted on 2010-10-02 15:18 Vontroy 阅读(245) 评论(0) 编辑收藏引用所属分类: 动态规划、POJ

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: POJ 1458 Common Subsequence 背包问题九讲

网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

随笔分类(55)