面试题库 › 算法 / 大模型 › 最长公共子序列(LeetCode 1143)

最长公共子序列(LeetCode 1143)

难度 ★★☆在 11 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

字节跳动3腾讯2美团1华为1大疆1蚂蚁集团1腾讯音乐1无界智索1

常见岗位:大模型算法、Java 后端、AI 应用 / Agent 开发、C++ 后端、C++ / Qt 客户端

答案要点

  1. dp[i][j]:第一个串前 i 个与第二个串前 j 个字符的 LCS 长度
  2. 字符相等:dp[i][j] = dp[i-1][j-1] + 1
  3. 不相等:dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  4. 边界:dp[0][*] = dp[*][0] = 0;答案 dp[m][n]
  5. 时间 O(m×n),空间可压缩到一维;回溯 dp 表可还原具体子序列

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题