贪心与动态规划

1. 一句话总结

贪心每步做局部最优，DP 通过状态和转移求全局最优。

2. 通俗解释

贪心像每次选眼前最划算的方案，前提是不会影响最终最优；DP 像填表，先算小问题再推大问题。

3. 核心概念

• 贪心：每一步选择当前最优。
• 动态规划：保存重叠子问题结果。
• 状态定义：dp[i] 或 dp[i][j] 表示什么。
• 状态转移：当前状态如何由历史状态推来。
• 初始化：最小子问题答案。
• 背包问题：容量限制下选择最大价值。

4. 底层原理

• 贪心需要证明局部最优能推出全局最优。
• DP 适用于最优子结构和重叠子问题。
• 记忆化搜索是自顶向下，表格 DP 是自底向上。
• 状态压缩利用状态只依赖少量历史信息。
• 0-1 背包一维优化通常倒序遍历容量。

5. 面试标准回答

贪心和动态规划都解决最优化问题，但思路不同。贪心每一步选择当前最优，只有局部最优能推出全局最优时才正确。动态规划把问题拆成重叠子问题，用状态保存结果，再通过状态转移得到答案。做 DP 题时要先定义状态含义，再确定转移方程、初始化和遍历顺序。面试中不能只说用 DP，必须讲清 dp 数组表示什么、为什么这样转移、边界如何处理。

6. 高频追问

追问 1：贪心与动态规划面试第一句话怎么答？

先给结论：贪心：每一步选择当前最优。 再补充它解决的问题和使用场景，避免一上来背长定义。

追问 2：它为什么需要底层机制支撑？

贪心需要证明局部最优能推出全局最优。 面试官追问时要把“现象”落到“机制”和“代价”。

追问 3：常见误区是什么？

不要把平均情况说成绝对结论，也不要忽略边界条件、退化情况和工程成本。

追问 4：如果继续追问怎么展开？

可以沿着“定义 → 原理 → 对比 → 场景 → 缺点 → 优化”展开，重点说清：DP 适用于最优子结构和重叠子问题。

追问 5：实际开发中怎么体现？

任务调度、区间选择常用贪心思想。 这类联系能把基础知识从“背概念”变成“解释工程选择”。

追问 6：回答时怎么收尾？

最后用一句话总结适用条件和代价，说明什么时候该用、什么时候不该用。

7. 易混淆点

8. 实际开发联系

• 任务调度、区间选择常用贪心思想。
• 资源分配、路径规划中常见 DP 建模。
• 复杂业务流程也可用状态建模思想分析。

9. 背诵速记

贪心看局部最优能否推出全局最优，DP 看最优子结构和重叠子问题。DP 四步：定义状态、写转移、初始化、确定遍历顺序。0-1 背包一维优化要倒序。