poj1458Common Subsequence最长公共子序列

动态规划的一个计算两个序列的最长公共子序列的方法如下： 以两个序列 X、Y 为例子： 设有二维 数组f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度，则有： f[1][1] = same(1,1); f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]} 其中，same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”，否则为“0”。 此时，二维数组中最大的数便是 X 和 Y 的最长公共子序列的长度，依据该 数组回溯，便可找出最长公共子序列。 该算法的空间、 时间复杂度均为O(n^2)，经过优化后， 空间复杂度可为O(n)。

 

1 #include <iostream> 2 #include <string.h> 3 using namespace std; 4 const int N = 305; 5 char str1[N], str2[N]; 6 int dp[N][N]; 7 8 int maxx(int a, int b, int c) 9 { 10 int t = a > b ? a : b; 11 return t > c ? t : c; 12 } 13 14 int same(int a, int b) 15 { 16 return a == b ? 1 : 0; 17 } 18 19 int main() 20 { 21 while (scanf("%s%s", str1, str2) == 2) 22 { 23 memset(dp, 0, sizeof(dp));//表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度 24 int len1 = strlen(str1), len2 = strlen(str2); 25 for (int i=1; i<=len1; i++) 26 for (int j=1; j<=len2; j++) 27 dp[i][j] = maxx(dp[i-1][j-1] + same(str1[i-1], str2[j-1]), dp[i-1][j], dp[i][j-1]); 28 printf("%d\n", dp[len1][len2]); 29 } 30 return 0; 31 }

 

转载于:https://www.cnblogs.com/lv-2012/archive/2013/05/11/3072945.html

相关资源：JAVA上百实例源码以及开源项目