最长公共子序列:填表与回溯

X = "ABCBDAB",Y = "BDCAB"。先按行填一张 dp 表(dp[i][j] = X 前 i 个字符与 Y 前 j 个字符的 LCS 长度),再从右下角往回走,回溯出真正的子序列长什么样。

0 / 0

dp[i][j] 表

未开始

两个字符串

X ="ABCBDAB"
Y ="BDCAB"

当前步骤

点击"下一步"或"播放"开始。

回溯出的最长公共子序列

尚未开始回溯
正在计算的格子 字符匹配时参照的左上格 回溯路径经过的格子
☕ 如果这篇文章帮到你,可以请作者喝杯咖啡 · 爱发电