最长公共子串的动态规划状态转移
哪些公司问过
答案要点
- 状态:dp[i][j] 为以 A[i]、B[j] 结尾的最长公共子串长度
- 转移:A[i]==B[j] 时 dp[i][j]=dp[i-1][j-1]+1,否则为 0
- 答案是整张表的最大值,并记录结束位置以还原子串
- 时间 O(mn);只依赖左上角,可压缩为一维(j 倒序)或两行滚动
- 与最长公共子序列的区别:子序列不等时取 max(dp[i-1][j], dp[i][j-1]),答案在 dp[m][n]
易错点
- 把答案写成 dp[m][n],那是以两串末尾结尾的长度,不是全局最长
- 与最长公共子序列混淆,不等时取了 max 而不是置 0
- 一维压缩时 j 正序遍历,或不相等时忘记把 dp[j] 置 0
面试官常见追问
- 一维压缩时为什么 j 要倒序?
- 有没有比 O(mn) 更快的方法?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场