【DP|LCS】POJ-1458 Common Subsequence

Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Description A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, x ij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y. Input The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. Output For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line. Sample Input abcfbc abfcab programming contest abcd mnp Sample Output 4 2 0 Source Southeastern Europe 2003

————————————————————吃饭的分割线————————————————————

思路：学习DP的基础——最长公共子序列。lrj的大白书上提到可以使用滚动数组进行优化，这里就顺便学习一下滚动数组。

考虑两个序列，从中找到最长的公共子序列，状态是——序列1的前 i 个元素和序列2的前 j 个元素能构成的最长公共子序列。

显然需要两个for循环来枚举序列1和序列2，最终的答案就是dp[l1][l2]了。

状态怎样转移呢？

假如当前的 i 、j 能够匹配，说明该元素可以加入子序列，这时候是从序列1的前 i - 1 个元素和序列2的前 j - 1 个元素能构成的最长公共子序列转移过来+1的。

那么加入当前的 i 、j 不能够匹配呢？说明该元素并不能加入子序列，状态从哪里转移过来？这时候有两种可能——前 i - 1 个元素和前 j 个元素构成的子序列最长；或者前 i 个元素和前 j - 1构成的子序列最长。为什么呢？

因为你并不知道是 i 能贡献一个元素还是 j 能贡献一个元素。例如：

A  B  C  B  D

B  D  C  A  B

看到了序列1最后一个D和序列2最后一个B的时候，显然是dp[i-1][j]转移过来更好。

状转方程：

If s1[i]==s2[j]
        dp[i][j] = dp[i-1][j-1] + 1
Else
        dp[i][j] = max{dp[i-1][j], dp[i][j-1]}           

而滚动数组则很简单，因为状转方程中对于 i ，只出现了[ i ]和[i-1]，因此可以用1和0代替。每次转移仅仅用得到"前一个 i "，因此可以滚动。

代码如下：

/****************************************/
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <algorithm>
 #include <cmath>
 #include <stack>
 #include <queue>
 #include <vector>
 #include <map>
 #include <string>
 #include <iostream>
 using namespace std;
/****************************************/
const int N = 501;
char s1[N], s2[N];
int dp[2][N];

int main()
{
	while(~scanf("%s%s", &s1[1], &s2[1])) {
		int l1 = strlen(s1+1), l2 = strlen(s2+1);
		//puts(s1+1);puts(s2+1);
		memset(dp, 0, sizeof(dp));
		for(int i = 1; i <= l1; i++)
			for(int j = 1; j <= l2; j++)
				if(s1[i] == s2[j])
					dp[i&1][j] = dp[!(i&1)][j-1] + 1;
				else
					dp[i&1][j] = max(dp[!(i&1)][j], dp[i&1][j-1]);
		printf("%d\n", dp[l1&1][l2]);
	}
	return 0;
}