1024:公共子序列

总时间限制: 1000ms 内存限制: 65536kB

描述

我们称序列Z = < z1, z2, …, zk >是序列X = < x1, x2, …, xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, …, ik >，使得对j = 1, 2, … ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。

现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。

输入

输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。

输出

对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。 样例输入

abcfbc abfcab programming contest abcd mnp

样例输出

4 2 0

动归的常用两种形式 1）递归型 优点:直观，容易编写 缺点:可能会因递归层数太深导致爆栈，函数调用带来额外时间开销。无法使用滚动数组节省空间。总体来说，比递推型慢。 1）递推型 效率高，有可能使用滚动数组节省空间

原问题分解成子问题，确定状态

输入两个串s1,s2, 设MaxLen(i,j)表示: s1的左边i个字符形成的子串，与s2左边的j个字符形成的子串的最长公共子序列的长度(i,j从O开始算） MaxLen(i,j)就是本题的“状态” 假定len1 = strlen(s1),len2= strlen(s2) 那么题目就是要求MaxLen(len1,len2)

确定一些初始状态（边界状态）的值 确定状态转移方程

证明maxLen(s1, s2)不会比maxLen(s1, s2_j-1)和maxLen(s1_i-1,s2)任何一个小，也不会比两者都大。

#include<bits/stdc++.h> using namespace std; char str1[205], str2[205]; int maxLen[205][205]; int main () { while (scanf("%s%s", str1, str2) == 2) { int len1 = strlen(str1); int len2 = strlen(str2); for (int i = 1; i <= len1; i++) for (int j = 1; j <= len2; j++) { if (str1[i-1] == str2[j-1]) maxLen[i][j] = maxLen[i-1][j-1] + 1; else maxLen[i][j] = max(maxLen[i-1][j], maxLen[i][j-1]); } printf("%d\n", maxLen[len1][len2]); } return 0; }