一句话理解
LCS 最长公共子序列。
为什么要学
二维 DP。
讲解
f[i][j]：s 前 i 与 t 前 j。相等则 f[i-1][j-1]+1，否则 max(上,左)。
例子
两个字符串对齐。
常见错误
- 当公共子串（连续）做。
- n=1e5 二维 n² MLE/TLE。
第 333 课
LCS
🔵 基础 约 7 分钟
练习 做完再看下一课
LCS 的经典 DP 是 O(nm)。
进度保存在本机浏览器里。
左右方向键也可翻课
第 333 课
LCS 最长公共子序列。
二维 DP。
f[i][j]：s 前 i 与 t 前 j。相等则 f[i-1][j-1]+1，否则 max(上,左)。
两个字符串对齐。
LCS 的经典 DP 是 O(nm)。
左右方向键也可翻课