动态规划与贪心有什么区别？｜腾讯后端开发面经解析

60 秒回答模板

可以这样回答：动态规划通过状态表保存子问题结果，依靠状态转移枚举可能选择；贪心每一步只做当前最优选择，并且必须能证明局部最优能导向全局最优。 DP 适合选择会相互影响、需要比较多个历史状态的问题；贪心适合存在交换论证、单调结构或可证明选择性质的问题。DP 常见复杂度更高，贪心通常更快但证明要求更强。能贪心时优先贪心，因为实现和复杂度更低；不能证明贪心正确时用 DP 更稳。面试中要能给反例说明错误贪心为什么失败。不要把所有求最优都说成贪心，也不要把所有有选择的问题都套 DP。关键是证明局部选择是否安全。验证时重点看：看状态转移、反例构造、交换论证、复杂度、空间优化和小规模枚举对拍。

考点 考点边界

主线 核心机制

易错点 只说 DP 看全局、贪心看局部，没有给状态转移和正确性…

深入解析

考点边界

这题必须围绕“动态规划与贪心区别”本身回答，不能套相邻大类模板。先给定义或目标，再展开机制、边界、取舍和验证抓手。回答时要主动点出题面关键词对应的对象、输入输出和约束条件，避免把具体问题讲成宽泛复习提纲。本题对应“动态规划与贪心区别”，核心前提是：动态规划通过状态表保存子问题结果，依靠状态转移枚举可能选择；贪心每一步只做当前最优选择，并且必须能证明局部最优能导向全局最优。

核心机制

DP 适合选择会相互影响、需要比较多个历史状态的问题；贪心适合存在交换论证、单调结构或可证明选择性质的问题。DP 常见复杂度更高，贪心通常更快但证明要求更强。关键证据要落到状态转移、不变量、边界用例、复杂度来源，这样才能说明机制为什么能支撑题目结论。如果继续展开，要说清状态定义、不变量、边界更新、终止条件和复杂度来源，并用反例说明为什么相邻做法不成立。

关键取舍

能贪心时优先贪心，因为实现和复杂度更低；不能证明贪心正确时用 DP 更稳。面试中要能给反例说明错误贪心为什么失败。因此要用输入规模、额外空间、最坏复杂度和边界用例来决定方案，而不是只背一个平均复杂度。这些取舍决定了方案在不同输入规模、延迟、内存、并发、泛化或一致性要求下是否仍然成立。

边界风险

不要把所有求最优都说成贪心，也不要把所有有选择的问题都套 DP。关键是证明局部选择是否安全。排查时优先用空输入、重复值、极端有序数据、溢出、内存上限和复杂度退化样例验证。需要特别关注极端输入、数据分布变化、资源不足、并发竞争或观测口径错误带来的退化。修复时要用最小反例复现错误，再检查边界条件、循环不变量、数据结构选择和复杂度退化点。

验证抓手

验证时要覆盖空输入、单元素、重复元素、边界溢出、极端有序或逆序数据，并明确时间复杂度和空间复杂度。能说出为什么这个复杂度成立，比只写伪代码更可靠。针对本题，最有价值的验证信号是：看状态转移、反例构造、交换论证、复杂度、空间优化和小规模枚举对拍。把验证抓手说出来，可以让答案从知识点延伸到算法正确性、复杂度和边界用例验证。

易错点

只说 DP 看全局、贪心看局部，没有给状态转移和正确性证明差异。
不会用反例说明错误贪心为什么失败，也没有证明局部选择为什么安全。
把相邻概念混用，没有明确说明这道题真正考察的边界。
没有给出验证方式，导致答案听起来完整但无法判断是否真的生效。

面试官追问

如何判断一个题能不能用贪心？

要证明当前局部选择不会破坏全局最优，常用交换论证或反证；没有证明时只能算猜策略。回答时还要补充适用前提、失败场景和验证信号，避免只给一个孤立结论。

DP 相比贪心的成本在哪里？

DP 要维护状态表并枚举转移，时间和空间通常更高，但能覆盖更多历史选择影响。回答时还要补充适用前提、失败场景和验证信号，避免只给一个孤立结论。

“动态规划与贪心有什么区别”继续追问时最该补哪条边界？

应该围绕“动态规划与贪心区别”补适用前提、失败场景和验证证据。先说明哪些条件下这个机制成立，再说明哪些输入规模、并发状态、数据分布或资源限制会让答案需要调整。

“动态规划与贪心有什么区别”怎样回答才不是只背概念？

看它能否把“动态规划与贪心区别”的机制链路、关键取舍和可观测信号连起来。回答时应落到具体状态变化、数据路径、复杂度、指标或排查工具，而不是只复述定义。

“动态规划与贪心有什么区别”怎么判断算法选型？

先看是否有最优子结构、单调性、局部选择是否会影响全局最优，以及数据结构能否降低查找或更新成本。动态规划、贪心、二分、哈希、堆和树结构分别对应不同的不变量。