1. 题目源地址：http://poj.org/problem?id=1458
2. 基本题意： 给出两个序列，求出最长子序列的长度并输出。经典的动态规划求解。
求最长公共子序列的经典DP解法代价为O(mn)，其中m和n分别为两个字符串的长度。具体实现如下表：
该表的建立自左而右，自上而下。规则建立如下：
（1）如果str1[i]＝str2[j]则将左上角元素值加1赋值给matrix[i][j]（自己），如果本身是最左上角元素就为1。
（2）如果str1[i]不等于str2[j]则该点元素值取matrix[i－1][j]和matrix[i][j－1]中较大的一个。
（3）如果i＝0且j＝0（最左上角）则取0。
下划线元素为最终取得的最长公共子序列。
动态规划方程：
3. 解题代码：
//POJ--1458:Common Subsequence 寻找最长公共子序列
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
int main()
{
char a[210],b[210];
int dp[210][210];
int len_a,len_b,i,j;
while(cin>>a>>b)
{
len_a=strlen(a);
len_b=strlen(b);
dp[0][0]=0;
for(i=1;i<=len_a;i++)
for(j=1;j<=len_b;j++)
{
if(a[i-1]==b[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
cout<<dp[len_a][len_b]<<endl;
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/163032.html
