(6)动态规划(上) LCS

LCS

问题描述: 在两个给定的序列中, 找出最长的公共子序列(Largest Common Sequence), 比如LCS(ABDCAC, BAACDC) = BCC(解不唯一);

分析

1. 最优子结构
   这个问题是具有最优子结构的特性的, 也就是说最后一阶段的那个大的结构, 是包含了前面的最优子结构的. 在LCS问题中, 最后最大的结构可以看成是A[m-1]和B[n-1]两个子序列, 再加上最后的a, b两个元素. 此时我们应该已经得到了LCS(A[m-1], B[n-1]), 那么最后阶段我们的决策就是要不要再延长这个子序列;

2. 递归式
   LCS(A[m], B[n]) =
   if a == b,
   LCS(A[m-1], B[n-1]) + a
   if a!=b
   max { LCS(A[m-1], {B[n-1]+b} ), LCS( {A[m-1]+a}, B[n-1]) }
   写得更简洁一些:
   c(i, j) = //Common, 返回值是LCS有多少个char
   (1) c(i-1, j-1) +1 , A[i] == B[j]
   (2) max{c(i-1, j), c(i, j-1)} , A[i] != A[j]
   (3) 0 , 边界条件i==0 || j==0 即出现有一条序列是长度为0的, 那么肯定公共序列长度为0;

3. 自底向上计算的算法

//输入: X, Y为两条序列
LCS(X[1~m], Y[1~n])
//初始化
let c[1~m][1~n] and rec[1~m][1~n] be new tables
for (i = 0~m)
    c[i][0] = 0
for (j = 0~n)
    c[0][j] = 0
//开始计算
for (i= 1~m)
    for (j= 1~n)
        if (X[i] == Y[j]) 
            c[i][j] = c[i-1][j-1] + 1
            rec[i][j] = 1 (↖️)
        else if (c[i-1][j] >= c[i][j-1])
            c[i][j] = c[i-1][j]
            rec[i][j] = 0 (↑)
        else 
            c[i][j] = c[i][j-1]
            rec[i][j] = 2 (←)
return c and rec

Print-LCS(rec[1~m][1~n], X[1~m], i, j)
if i==0 or j==0
    return 
if rec[i, j] == 1 (↖️)
    Print-LCS(rec, X, i-1, j-1)
    printf (X[i])    //因为讲求顺序, 因此从后往前找的时候, 先发现的后打印, 才能形成正确的顺序;
if rec[i, j] == 0 (↑)
    Print-LCS(rec, X, i-1, j)
else  (←)
    Print-LCS(rec, X, i, j-1)