动态规划高频追问 Q&A

A: 出现“最优解 + 重复子问题 + 子问题有重叠”时优先考虑 DP。（深入阅读：动态规划基础知识速览、何时考虑动态规划）

A: 先问“答案和谁有关”。通常从“以 i 结尾/到 i 为止/区间 i~j”三类定义切入。（深入阅读：状态设计的常见维度、线性 DP）

A: 用“最后一步”思维，把当前决策拆成互斥情况，再取 max/min/sum。（深入阅读：从暴力搜索推导状态、背包 DP）

A: 当 dp[i][j] 只依赖上一行或当前行左侧时可滚动数组；关键是遍历顺序正确。（深入阅读：背包 DP、线性 DP）

A: 贪心每步只看局部最优；DP 会比较多条历史路径并保留全局最优状态。（深入阅读：动态规划基础知识速览、贪心基础知识速览）

A: 先写状态语义、边界、转移，再手推 2~3 个小样例验证。（深入阅读：动态规划面试表达模板、线性 DP）

A: 分治的子问题通常相互独立，动态规划的子问题有重叠并需要复用结果；都可用递归实现，但状态依赖和缓存方式不同。（深入阅读：分治、动态规划、贪心和回溯的区别、复杂度分析方法与陷阱）

A: 局部最优未必推出全局最优，必须用交换论证、反证或其他正确性证明；无法证明时应考虑 DP 或搜索。（深入阅读：贪心基础知识速览、区间贪心）

动态规划 高频追问 Q&A