面试题库 › C++ / 后端 › 最长公共子串的动态规划状态转移

最长公共子串的动态规划状态转移

难度 ★★☆在 1 场真实面经中被问到 方向:C++ / 后端考点:动态规划

哪些公司问过

网易1

常见岗位:C/C++ 软件开发

答案要点

  1. 状态:dp[i][j] 为以 A[i]、B[j] 结尾的最长公共子串长度
  2. 转移:A[i]==B[j] 时 dp[i][j]=dp[i-1][j-1]+1,否则为 0
  3. 答案是整张表的最大值,并记录结束位置以还原子串
  4. 时间 O(mn);只依赖左上角,可压缩为一维(j 倒序)或两行滚动
  5. 与最长公共子序列的区别:子序列不等时取 max(dp[i-1][j], dp[i][j-1]),答案在 dp[m][n]

易错点

面试官常见追问

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

相关面试题