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

求最長公共子序列 狀態(tài)轉(zhuǎn)移方程 dp[i][j] 是在i的當(dāng)前字符，和j的當(dāng)前字符相對于前面 1~i-1 1~j-1里面最長的公共子序列。 因?yàn)轭}目要求的公共子序列的兩個(gè)條件是 在s里面是有次序的，在s2里面也是有次序，過了的不能再被選擇，只能不斷往后選。相當(dāng)于兩個(gè)上升序列合并，但是選擇條件改變了。而那些不相同的 保持的是上一個(gè)相同的最大值。 遇到兩個(gè)相同的值，dp[i][j] 由s的上一個(gè)字符階段 i-1 里面選擇 j在1~j-1字符里面的最長公共序列里面選擇最長的dp，由于j-1是j在 1到j(luò)-1里面最長的 所以 dp[i-1][j-1]是上一個(gè)相同字符里面最長的。 為什么j-1 是1~j-1里面最長的 因?yàn)?dp[i][j] =max(dp[i-1][j],dp[i-1][j-1]),從而得到無論是i的上一階段還是當(dāng)前階段i也是最長的，而且 與（1~j-1）也是最長的那個(gè)。 if(s[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]);}