问题建模
把子问题定义为：
c[i][j] 表示 X[1..i]与 Y[1..j] 的 LCS 长度。
再用一个标记表 b[i][j] 记录转移方向，便于回溯得到具体序列。
递推方程
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]= \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）
复杂度
时间复杂度 \mathcal{O}(mn) ，空间复杂度 \mathcal{O}(mn)。
实例填表
备忘录表C
标记表B
LCS=⟨a,c,b,b⟩,长度：4 。