动态规划:最长公共子序列 (LCS)

编辑于 2017-03-19

* 移动设备下, 可左滑手指以查看较宽代码

一个字符串 S,去掉零个或者多个元素所剩下的子串称为 S 的子序列。最长公共子序列就是寻找两个给定序列的子序列,该子序列在两个序列中以相同的顺序出现,但是不必要是连续的。

例如序列 X=ABCBDAB,Y=BDCABA。序列 BCA 是 X 和 Y 的一个公共子序列,但是不是 X 和 Y 的最长公共子序列,子序列 BCBA 是 X 和 Y 的一个 LCS,序列 BDAB 也是。

分析

考虑最长公共子序列问题如何分解成子问题,设 A=“a0,a1,…,am-1”,B=“b0,b1,…,bm-1”,并 Z=“z0,z1,…,zk-1” 为它们的最长公共子序列。则:

1) 如果 am-1=bn-1,则 zk-1=am-1=bn-1,且 “z0,z1,…,zk-2” 是 “a0,a1,…,am-2” 和 “b0,b1,…,bn-2” 的一个最长公共子序列;

2) 如果 am-1!=bn-1,则若 zk-1!=am-1,蕴涵 “z0,z1,…,zk-1” 是 “a0,a1,…,am-2” 和 “b0,b1,…,bn-1” 的一个最长公共子序列;

3) 如果 am-1!=bn-1,则若 zk-1!=bn-1,蕴涵 “z0,z1,…,zk-1” 是 “a0,a1,…,am-1” 和 “b0,b1,…,bn-2” 的一个最长公共子序列。

这样,在找 A 和 B 的公共子序列时,如有 am-1=bn-1,则进一步解决一个子问题,找 “a0,a1,…,am-2” 和 “b0,b1,…,bm-2” 的一个最长公共子序列;如果 am-1!=bn-1, 则要解决两个子问题,找出 “a0,a1,…,am-2” 和 “b0,b1,…,bn-1” 的一个最长公共子序列和找出 “a0,a1,…,am-1” 和 “b0,b1,…,bn-2” 的一个最长公共子序列,再取两者中较长者作为 A 和 B 的最长公共子序列。

故而状态转移方程为:

dp[i][j] = 0  如果 i=0 或 j=0
dp[i][j] = dp[i-1][j-1] + 1  如果 X[i-1] = Y[i-1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1])  如果 X[i-1] != Y[i-1]

代码

for(int i = 0;i <= A.size();i++)
    len[i].resize(B.size()+1,0);

for (int i = 1; i <= A.size(); ++i) {
    for (int j = 1; j <= B.size(); ++j) {
        if (A[i - 1] == B[j - 1])
            len[i][j] = len[i - 1][j - 1] + 1;
        else if (len[i - 1][j] >= len[i][j - 1])
            len[i][j] = len[i - 1][j];
        else
            len[i][j] = len[i][j - 1];
    }
}