动态规划 高频追问 Q&A
1. Q: 什么时候应该想到用动态规划？
A: 出现“最优解 + 重复子问题 + 子问题有重叠”时优先考虑 DP。
2. Q: 状态定义总写不出来怎么办？
A: 先问“答案和谁有关”。通常从“以 i 结尾/到 i 为止/区间 i~j”三类定义切入。
3. Q: 转移方程如何推导？
A: 用“最后一步”思维，把当前决策拆成互斥情况，再取 max/min/sum。
4. Q: 为什么有的题能降维到一维？
A: 当 dp[i][j] 只依赖上一行或当前行左侧时可滚动数组；关键是遍历顺序正确。
5. Q: DP 和贪心怎么区分？
A: 贪心每步只看局部最优；DP 会比较多条历史路径并保留全局最优状态。
6. Q: 面试时如何快速写稳？
A: 先写状态语义、边界、转移，再手推 2~3 个小样例验证。