最长公共子序列 LCS 动画讲解
以 X = ACEFOP、Y = COEABFP 为例，演示 `dp[i][j]` 如何从空串边界一步步填满，并从右下角回溯出一个最长公共子序列。
核心结论
双序列线性 DPX
Y
DP 数组
7 × 8
主表格
8 × 9
LCS 长度
4
一个 LCS
CEFP
状态定义与转移
dp[i][j]dp[i][j] = X 前 i 个字符 与 Y 前 j 个字符的 LCS 长度
if (X[i] == Y[j]):
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
当前正在计算的格子
已经计算出的格子
当前转移参考的格子
回溯得到 LCS 的路径
DP 填表动画
初始化当前步骤说明
dp[0][0]初始化边界
当其中一个字符串为空时，最长公共子序列长度为 0，因此第 0 行和第 0 列都是 0。
dp[0][j] = 0, dp[i][0] = 0