首页 > 其他 > 详细

POJ 1458

时间:2016-04-21 20:26:09      阅读:157      评论:0      收藏:0      [点我收藏+]

http://poj.org/problem?id=1458

 

一道容易的DP,求最长公共子序列的

dp[i][j],代表str1中的第i个字母和str2中的第j个字母的最多的公共字母数

 

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string.h>
 4 
 5 using namespace std;
 6 int dp[500][500]={0};
 7 
 8 int main()
 9 {
10     char str1[500],str2[500];
11     while(~scanf("%s %s",str1,str2))
12     {
13      /*   scanf("%s",str1)
14         scanf("%s",str2);*/
15         int len1=strlen(str1);
16         int len2=strlen(str2);
17         for(int i=1;i<=len1;i++)
18             for(int j=1;j<=len2;j++)
19         {
20             if(str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]+1; //这个就是那个递推公式,但str1[i-1]和str2[j-1]想等于时dp[i][j]就会等于前一个加一,不等就是等于前面的最大的一个
21             else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
22         }
23         printf("%d\n",dp[len1][len2]);
24     }
25     return 0;
26 }

 

POJ 1458

原文:http://www.cnblogs.com/Tree-dream/p/5418383.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!