动态规划——最长公共子序列&&最长公共子串

最长公共子序列（LCS）是一类典型的动归问题。
问题

给定两个序列（整数序列或者字符串）A和B，序列的子序列定义为从序列中按照索引单调增加的顺序取出若干个元素得到的新的序列，比如从序列A中取出 A[i1], A[i2], ...A[ik]，其中0=< i1 <= i2 <= ... ik <= n-1得到的新的序列 A[i1].A[i2]....A[ik]即为A的一个子序列。
两个不同的原序列A和B可能有着相同的子序列，求出A和B的公共子序列的最长长度。

分析
这种“离散”性质，且有子结构的问题，考虑用动态规划来解决。定义“状态”： dp[i][j]表示序列A的前缀 A[0....i]和序列B的前缀B[0....j]含有的最长公共子序列的长度。则有递推关系：

    dp[i][j] = dp[i-1][j-1] + 1; if (A[i] == B[j])
    dp[i][j] = max{dp[i-1][j], dp[i][j-1]} if (a[i] != B[j])

    对于递推关系的说明：
    显然，若A[i] == B[j]，A[0....i]和B[0...j]构成的最长公共子序列的长度为A[0...i-1]和B[0....j-1]的最长公共子序列的长度+1；如果A[i] != B[j]，则可以证明 dp[i][j] >= dp[i-1][j], dp[i][j] >= dp[i][j-1]。这是因为 A[0...i]&&B[0....j]包含了A[0...i]&&B[0....j-1] 显然长度较长的两个子串的LCS要长于长度较短的两个子串的LCS。于是dp[i][j] >= max{dp[i-1][j], dp[i][j-1]}。
    再说明 dp[i][j] <= max{dp[i][j-1], dp[i-1][j]}。
    (1)首先，易证一个事实

A[0....t1]&B[0...p1]的最长公共子串的长度len1 大于 A[0...t2]&B[0...p2]的最长公共子串的长度len2，如果t1 >= t2 且p1 >= p2

(2)然后，如上图所示。假设dp[i][j-1] >= dp[i-1][j],若 dp[i][j] > dp[i][j-1]，则B[j]肯定与A[t…i-1]中的某个数相同，其中t为A[0...i]和B[0...j-1]的公共子串的最后一个元素的位置。假设为A[k]，那么，此时A[0...i-1]和B[0….j]的公共子串的的范围（A中是A[0….k]，B中是B[0….j]）要大于A[0...i]和B[0….j-1]公共子串的范围（A中是A[0…t],B中是B[0...j-1），于是dp[i-1][j] >= dp[i][j-1]，与前提矛盾！

实现

memset(dp, 0, sizeof(dp));
dp[0][0] = (A[0] == B[0]);
if(A[1] == B[0] || A[0] == B[0])
    dp[1][0] = 1;
if(B[1] == A[0] || B[0] == A[0])
    dp[0][1] = 1;
for(int i = 1; i < n; i ++){
    for(int j = 1; j < m; j ++){
        if(A[i] == B[j])
            dp[i][j] = dp[i-1][j-1] + 1;
        else
            dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
    }
}

最长公共子串 Longest Common Substring

它是最长公共子序列问题的一种特例，需要找出最长的公共的连续的一段字符构成的子串。状态dp[i][j] 表示 str1和str2中分别以 str1[i] 和 str2[j] 结尾的最长公共子串长度，它的递推公式为：

dp[i][j] = dp[i-1][j-1] + 1; 如果 str1[i] == str2[j]

dp[i][j] = 0; 如果 str1[i] != str2[j]

result = max(dp[i][j], result)