动态规划如何回溯出具体方案
哪些公司问过
答案要点
- dp 只给出最优值,回溯从终态出发反推每一步的最优决策
- 方法一:填表时记录 parent / choice 数组,终点沿数组倒推再反转
- 方法二:利用转移方程重新判断,如背包中 dp[i][j] ≠ dp[i−1][j] 说明选了第 i 件
- 滚动数组会覆盖中间状态,需保留完整表或单独存决策
- 存在多个最优解时可在回溯时 DFS 枚举所有满足条件的前驱
易错点
- 用了滚动数组后才想回溯,发现中间状态已丢失
- 回溯时边界和下标处理错误,比如 i、j 的偏移与填表时不一致
- 记录的路径是逆序的,忘记反转就直接输出
面试官常见追问
- 要输出所有最优方案怎么办?
- 空间压缩后还想回溯有什么办法?
- 如何要求字典序最小的方案?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场