分割回文串的最少子串数(最少分割次数)
哪些公司问过
网易有道1MiniMax1
答案要点
- dp[i] 表示前 i 个字符的最少回文子串数,dp[0]=0,答案为 dp[n]
- 转移:dp[i] = min(dp[j]+1),要求 s[j..i-1] 为回文
- 用区间 DP 预处理回文表,isPal[j][i] 依赖 isPal[j+1][i-1],j 需从大到小遍历
- 时间 O(n²)、空间 O(n²);中心扩展边扩边更新 dp 可把空间降到 O(n)
- 若题目问最少分割次数,结果为最少子串数减 1
易错点
- 混淆最少子串数和最少分割次数,两者相差 1
- 回文表填表顺序错误,用到了尚未计算的状态
- 每次转移都现场判断回文,导致复杂度退化到 O(n³)
面试官常见追问
- 如果要输出一种具体的最优拆分方案怎么办?
- 要求输出所有回文拆分方案(力扣 131)呢?
- 为什么回文表要按 j 从大到小填?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场