← 演示目录

LCS 填表

DP 专题

X=ABCBDAB,Y=BDCABA。c[i][j]:X 前 i 与 Y 前 j 的 LCS 长。相等取左上 +1;否则取 max(上,左),平局取上。终格 4。回溯一条 BCBA。整表预计算。DP 不单列进 408 数据结构。

STEP 0
READY先填表,再回溯。