问题建模

把子问题定义为：
c[i][j]c[i][j] 表示 X[1..i]X[1..i]与 Y[1..j]Y[1..j] 的 LCS 长度。

再用一个标记表 b[i][j]b[i][j] 记录转移方向，便于回溯得到具体序列。

递推方程

c[i][j]={0,i=0 或 j=0,c[i−1][j−1]+1,xi=yj,max⁡{c[i−1][j], c[i][j−1]},xi≠yj.c[i][j]= \begin{cases} 0, & i=0 \text{ 或 } j=0,\\ c[i-1][j-1]+1, & x_i=y_j,\\ \max\{c[i-1][j],\, c[i][j-1]\}, & x_i\ne y_j. \end{cases}
b[i][j]={↖,若 xi=yj （来自对角线）,↑,若 xi≠yj 且 c[i−1][j]≥c[i][j−1],←,否则（来自左边）.b[i][j]= \begin{cases} \nwarrow, & \text{若 } x_i=y_j\ \text{（来自对角线）},\\ \uparrow, & \text{若 } x_i\ne y_j \text{ 且 } c[i-1][j]\ge c[i][j-1],\\ \leftarrow, & \text{否则（来自左边）}. \end{cases}

伪代码

LCS-Length-and-Path(X[1..m], Y[1..n]):
    创建数组 c[0..m][0..n] ← 0
    创建数组 b[0..m][0..n]

    for i = 1..m:
        for j = 1..n:
            if X[i] == Y[j]:
                c[i][j] = c[i-1][j-1] + 1
                b[i][j] = '↖'
            else if c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
                b[i][j] = '↑'
            else:
                c[i][j] = c[i][j-1]
                b[i][j] = '←'

    # 回溯输出一个最优解
    i ← m; j ← n; S ← 空栈
    while i>0 and j>0:
        if b[i][j] == '↖':
            将 X[i] 压入栈 S
            i ← i-1; j ← j-1
        else if b[i][j] == '↑':
            i ← i-1
        else:  # '←'
            j ← j-1
    输出从栈 S 依次弹出的序列（即 LCS）

复杂度

时间复杂度 O(mn)\mathcal{O}(mn) ，空间复杂度 O(mn)\mathcal{O}(mn)。

实例填表

备忘录表C

X\Y

∅

a

c

b

b

∅

0

0

0

0

0

a

0

1

1

1

1

b

0

1

1

2

2

c

0

1

2

2

2

b

0

1

2

3

3

d

0

1

2

3

3

b

0

1

2

3

4

标记表B

X\Y

∅

a

c

b

b

∅

-

-

-

-

-

a

-

↖

←

←

←

b

-

↑

↑

↑

↑

c

-

↑

↖

↑

↑

b

-

↑

↑

↖

↖

d

-

↑

↑

↑

↑

b

-

↑

↑

↖

↖

LCS=⟨a,c,b,b⟩,LCS=⟨a,c,b,b⟩,长度：44 。