最长公共子序列
使用 DP 表对齐两个字符串
最长公共子序列 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
什么是子序列
子序列会保持字符的顺序，但可以跳过某些字符。从 'abcde' 中可以选出 'ace'，但绝不可能选出 'aec'。
LCS 的目标
给定两个字符串，最长公共子序列是同时出现在两个字符串中、且相对顺序相同的最长序列。
转到网格
比较两个字符串的前缀。根据它们的长度构建一个二维表格，就能将问题转化为熟悉的网格 DP。
定义状态
令 dp[i][j] 表示字符串 A 的前 i 个字符与字符串 B 的前 j 个字符的 LCS 长度。
字符匹配时
如果 A[i-1] 等于 B[j-1]，这个共同字符会让 LCS 延长。您需要将对角线上的值 dp[i-1][j-1] 加一。
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1字符不同时
如果字符不同，就从任一字符串中删去一个字符，并保留较好的结果。您需要取两个相邻值中的最大值。
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])基本情况
空前缀不包含任何共同字符，因此 LCS 长度为零。第 0 行和第 0 列都保持为零。
dp = [[0] * (m+1) for _ in range(n+1)]多出一行一列
将表格设置为 n+1 行、m+1 列，就能得到一圈免费的零边界。这样可以省去边缘处繁琐的边界检查。
填满表格
让 i 和 j 从 1 开始递增遍历。每个单元格只需要上方、左侧和对角线上的值，而这些值都已经计算完成。
for i in range(1, n+1):
for j in range(1, m+1):
...读取长度
完整的 LCS 长度位于右下角。所有单元格填充完成后，答案就是 dp[n][m]。
length = dp[n][m]复杂度
您只需访问每个单元格一次，因此时间和内存复杂度都是 O(n 乘以 m)。这可以轻松处理长度达几千的字符串。
快速检查
当前字符 A[i-1] 和 B[j-1] 相等。哪种更新方式是正确的？
回顾：LCS
构建一张 n+1 行、m+1 列的表格：匹配时将对角线值加一，否则取相邻值中的最大值。右下角存放着长度。🔗
常见问题解答
「最长公共子序列」课时是免费的吗？
是的 — 「最长公共子序列」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「最长公共子序列」这节课中我会学到什么？
使用 DP 表对齐两个字符串 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「最长公共子序列」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 网格路径计数
- 带障碍物的最小路径和
- 最长公共子序列
- 逐步理解编辑距离