01

60 秒回答模板

贪心是每一步做当前看起来最优的选择，并且必须证明这个选择不会排除全局最优，常用交换论证或反证法；动态规划是把问题拆成有重叠子问题和最优子结构的状态集合，通过状态定义、转移方程、初始化边界和遍历顺序复用计算结果。两者都可能利用最优子结构，但贪心只保留一条决策路径，DP 会保留足够多的中间状态。无法证明局部选择安全、当前选择会影响未来时，通常优先考虑 DP 或搜索。

考点 核心机制与工程取舍
难度 中高频面试题
回答目标 按定义、机制、场景讲清楚
02

深入解析

01

贪心要证明选择性质

贪心不是凭直觉选最大或最小，而是要证明存在一个最优解包含当前选择。区间调度按结束时间最早选择，就是因为它给后续留下最多空间。

02

DP 要定义状态而不是套模板

DP 的核心是 `dp[i]` 或 `dp[i][j]` 表示什么。状态定义错了，转移再漂亮也不成立。定义后再写转移、初始化、遍历顺序和答案位置。

03

两者的保存信息不同

贪心每轮丢弃大量候选，只保留当前路径；DP 保存多个子问题结果，让未来选择可以比较不同历史。0/1 背包通常不能只按性价比贪心，因为局部选择可能挤掉更优组合。

04

无后效性和重叠子问题是 DP 信号

如果未来只依赖当前状态而不依赖到达该状态的具体路径，就有无后效性；如果大量子问题会重复出现，就适合记忆化搜索或表格 DP。

05

遍历顺序决定能否正确复用

0/1 背包容量要倒序，避免同一物品在一轮里被重复使用；完全背包容量可正序，允许重复选择。面试里这类细节能区分会背和会写。

03

易错点

  • 把贪心当成每次选最大或最小，却没有正确性证明。
  • DP 状态含义不清，导致转移方程没有可验证语义。
  • 初始化和遍历方向写错，尤其背包问题中重复使用同一物品。
  • 只说最优子结构，漏掉重叠子问题和无后效性。
04

面试官追问

贪心为什么一定要证明？

局部最优不天然推出全局最优。证明要说明把任意最优解替换成当前选择后不会更差，或反证当前选择不可能伤害最优性。

DP 三要素是什么？

状态定义、状态转移、边界初始化。实际写题还要补遍历顺序、答案位置和空间优化口径。

为什么 0/1 背包不能简单按性价比贪心？

容量是离散约束，局部性价比最高的物品可能占用容量，导致更高总价值组合无法选择，所以要比较不同容量下的最优状态。

记忆化搜索和表格 DP 怎么选？

状态转移天然递归、有效状态较少时记忆化更直观；状态空间规则且需要控制遍历顺序时表格 DP 更清晰。