贪心算法与 DP：何时使用哪一种
利用贪心选择性质和交换论证，识别适合用贪心算法解决的问题，以及必须使用 DP 的问题。
贪心算法与 DP：何时使用哪一种 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
贪心与 DP 概览
贪心和动态规划都用于解决优化问题——寻找最大值、最小值或最优安排。贪心算法在每一步都做出局部最优选择，而不会重新考虑之前的决策。DP 会探索所有可能性，但使用记忆化来避免重复计算。了解该选择哪种方法，可以避免花费数小时调试错误的贪心算法，或构建不必要的复杂 DP 表。
# Greedy: always take the locally best option
# Example: coin change with coins [1, 5, 10, 25]
# Greedy: take as many 25s as possible, then 10s, etc.
# This works for standard denominations but NOT all coin sets!
# DP: explore all possibilities via memoisation
# Example: coin change with coins [1, 3, 4] and target 6
# Greedy would pick 4, then 1, 1 → 3 coins
# DP finds: 3 + 3 → 2 coins (optimal!)
print('Greedy can fail when local optimum != global optimum')贪心选择性质
当一个全局最优解总能通过做出局部最优（贪心）选择来构造时，这个问题就具有贪心选择性质。形式上说：存在一个以贪心选择开头的最优解，因此我们永远不需要 backtrack。证明这一点通常使用交换论证：假设某个最优解没有包含贪心选择，然后证明可以将该选择交换进去，而不会使结果变差。
# Exchange argument example: Activity Selection
# Greedy: always pick the activity that ends earliest
# Proof: suppose optimal solution starts with activity A (not earliest-ending)
# Let G be the earliest-ending activity.
# Replace A with G in the solution:
# - G ends no later than A, so G does not conflict with any activity A allowed
# - The solution remains valid with at least as many activities
# Therefore greedy choice (earliest end) is always safe.
activities = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14)]
activities.sort(key=lambda x: x[1]) # sort by end time
print('Sorted by end:', activities[:4], '...')最优子结构
贪心算法和 DP 都要求具有最优子结构：完整问题的最优解包含各个子问题的最优解。区别在于，子问题的最优解能否通过贪心方式确定（无需探索所有选项），还是必须比较多个选择。如果做出一个选择后，剩余子问题的结构保持不变，那么贪心算法通常有效。如果必须比较多个选择，则应使用 DP。
# Greedy works: activity selection
# Making the greedy choice (earliest-ending) leaves a sub-problem
# that is structurally identical (activity selection on remaining activities)
# and the greedy choice for the sub-problem is still valid.
# DP needed: 0/1 knapsack
# After choosing to include/exclude item i, the remaining sub-problem
# depends on WHICH item we chose — different choices yield different sub-problems.
# No single greedy rule works for all inputs.
print('Greedy: sub-problem is unique after each choice')
print('DP: sub-problem depends on which choice was made')重叠子问题是 DP 信号
如果在递归分解中，同一个子问题被求解多次，就需要使用带记忆化的 DP。画出递归树，并查找重复出现的节点。对于斐波那契数列，在计算 fib(5) 的递归树中，fib(3) 会被计算两次。对于硬币找零问题，硬币为 [1,3,4]、目标值为 6 时，目标值为 3、2、1 的子问题会多次出现。重叠子问题加上最优子结构 = DP。
# Recursion tree for coin change [1,3,4], target=6
# bt(6) → bt(5) → bt(4) → bt(3) (repeated!)
# → bt(2) → bt(1) (repeated!)
# → bt(3) (repeated!)
# → bt(2) (repeated!)
# Without memoisation: exponential time
# With DP table: O(target * len(coins)) time
def coin_change_dp(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change_dp([1, 3, 4], 6)) # 2 (3+3)
print(coin_change_dp([2], 3)) # -1 (impossible)经典贪心问题
以下问题可以证明贪心算法一定正确：(1) 活动/区间调度——使用最早结束时间的贪心策略。(2) 最小生成树——Prim 和 Kruskal 算法。(3) 霍夫曼编码——始终合并频率最低的两个节点。(4) 分数背包——按价值/重量比最高的顺序选择物品。(5) 跳跃游戏——跟踪最远可达的索引。所有这些问题都可以通过交换论证来证明正确性。
# Fractional Knapsack: greedy works
def fractional_knapsack(items, capacity):
# Sort by value/weight ratio descending
items.sort(key=lambda x: x[1]/x[0], reverse=True)
total = 0
for weight, value in items:
if capacity <= 0: break
take = min(weight, capacity)
total += take * (value / weight)
capacity -= take
return total
items = [(10, 60), (20, 100), (30, 120)] # (weight, value)
print(fractional_knapsack(items, 50)) # 240.0
# 0/1 Knapsack: greedy FAILS
# Must use DP (can't take fractions)贪心失效时：反例
寻找反例是推翻贪心假设的最快方法。对于硬币为 [1, 3, 4]、目标值为 6 的硬币找零问题，贪心算法（优先选择最大面额）会先取 4，然后取 1+1，共使用 3 枚硬币；DP 则找到 3+3，只需 2 枚硬币。对于 0/1 背包问题，按比率使用贪心策略会选择比率最高的物品，但可能错过能更好填满容量的组合。如果您能在一分钟内构造出反例，就应切换到 DP。
# Counterexample: coin change with non-standard coins
def greedy_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for c in coins:
while amount >= c:
amount -= c
count += 1
return count if amount == 0 else -1
def dp_coins(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a: dp[a] = min(dp[a], dp[a-c] + 1)
return dp[amount] if dp[amount] < float('inf') else -1
coins, target = [1, 3, 4], 6
print('Greedy:', greedy_coins(coins[:], target)) # 3 (4+1+1)
print('DP: ', dp_coins(coins, target)) # 2 (3+3)对比表：贪心与 DP
两者的主要区别如下：Time 复杂度——贪心算法通常为 O(n log n)（主要由排序决定）；DP 为 O(n × 状态数)。空间复杂度——贪心算法的辅助空间为 O(1)；DP 为 O(状态数)。正确性——贪心算法需要证明；只要状态和递推关系正确，DP 始终正确。适用场景——贪心算法适用于调度、生成树和霍夫曼编码；DP 适用于背包、序列对齐以及带负权重的最短路径。
# Performance comparison
import time
def time_it(func, *args):
start = time.time()
result = func(*args)
return result, time.time() - start
# Large coin change test
coins = [1, 5, 10, 25, 100]
amount = 10000
def dp_coins(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a: dp[a] = min(dp[a], dp[a-c]+1)
return dp[amount]
result, elapsed = time_it(dp_coins, coins, amount)
print(f'DP coin change(amount={amount}): {result} coins in {elapsed:.4f}s')决策框架
面试中的决策流程如下：(1) 您能否通过交换论证证明贪心选择性质？如果能 → 使用贪心算法。(2) 子问题是否重叠（同一状态是否通过多种方式到达）？如果是 → 使用 DP。(3) 问题是否要求计数或枚举所有解？→ 使用 DP 或回溯。(4) 问题是否要求一个具有自然顺序的单一最优值？可以优先考虑贪心算法。(5) 如果无法确定，就编写 DP——只要递推关系正确，它始终正确，即使速度较慢。
# Decision questions to ask:
questions = [
'1. Is there a natural ordering (by time, ratio, size)?',
'2. Does making the greedy choice leave a smaller same-type problem?',
'3. Can I construct a counterexample quickly?',
'4. Are sub-problems reused across different choice sequences?',
'5. Does the problem involve counting or listing (not just optimising)?',
]
for q in questions:
print(q)
print()
print('Greedy signals: scheduling, spanning tree, Huffman, jump game')
print('DP signals: knapsack, edit distance, LCS, coin change (general)')区间问题：贪心与 DP
区间问题可以分为贪心类和 DP 类。不重叠区间（移除最少区间）：按结束时间 sort，然后使用贪心策略选择区间——这种方法可以证明是最优的。带权区间调度（最大化总权重）：需要使用 DP，因为高权重区间可能与许多低权重区间重叠，需要比较所有有效子集。区分两者的关键在于，所有区间是否具有相同权重（贪心）还是不同权重（DP）。
# Non-overlapping intervals: greedy works
def erase_overlap_intervals(intervals):
if not intervals: return 0
intervals.sort(key=lambda x: x[1])
count = 0
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
last_end = end # keep this interval
else:
count += 1 # remove this interval
return count
print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]])) # 1
print(erase_overlap_intervals([[1,2],[1,2],[1,2]])) # 2识别问题信号
常见的问题描述信号包括：“最少操作次数”、“最大利润”、“最优选择” → 可能使用贪心或 DP，需要检查是否存在重叠。“计算方案总数” → 总是考虑 DP。“找到任意有效调度” → 可能使用贪心。“所有可能的方案” → 使用回溯。“不能选择相邻项” → 使用 DP（打家劫舍问题）。“会议、区间、任务” → 很可能使用贪心。将这些信号映射到算法类别，可以加快面试题的分析速度。
# Signal-to-algorithm mapping
signals = {
'minimum steps/coins/operations': 'DP (unless trivially greedy)',
'maximum profit/value with constraint': 'DP (knapsack family)',
'count ways to reach/achieve': 'DP (always)',
'all combinations/permutations': 'Backtracking',
'schedule tasks within time': 'Greedy (sort by deadline/end)',
'cannot pick adjacent': 'DP (house robber pattern)',
'free to pick any subset': 'DP or Greedy (check overlap)',
'interval merging/selecting': 'Greedy (sort by end time)',
}
for signal, algo in signals.items():
print(f'{signal!r}: → {algo}')证明贪心算法的正确性
要证明贪心算法正确，请使用交换论证：(1) 假设存在一个最优解 OPT，它在第一个选择处与贪心解 G 不同。(2) 证明可以将贪心选择交换到 OPT 中，而不会增大目标值。(3) 通过归纳法，证明贪心解与任何最优解一样好。在面试中，您不需要给出完整证明，但说明交换论证的直觉可以体现您对问题的深入理解。
# Exchange argument demo: earliest-finish-time activity selection
# Suppose OPT starts with activity A (not earliest-ending)
# Let G = earliest-ending activity available
# A.end >= G.end (G ends earlier or same time)
# Swap A for G in OPT:
# - G.end <= A.end, so G does not conflict with anything A allowed after it
# - OPT remains valid with the same number of activities
# - Repeat: after swap, OPT begins with G, matching greedy first choice
# By induction, OPT can be transformed to match G activity by activity
# without losing activities → greedy is optimal
print('Exchange argument: any OPT can be modified to match Greedy without loss')
print('This proves Greedy >= OPT in objective value')快速检查
测试您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学习了：当贪心选择性质成立时，贪心算法是正确的，这可以通过交换论证证明；当子问题重叠（同一个子问题通过多种方式到达）且无法通过单一贪心规则解决时，需要使用 DP；以及证明贪心假设错误的最快方法，是使用非典型输入构造反例。接下来，我们将使用按结束时间 sort 的方法解决区间调度与区间合并问题。
常见问题解答
「贪心算法与 DP：何时使用哪一种」课时是免费的吗？
是的 — 「贪心算法与 DP：何时使用哪一种」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「贪心算法与 DP：何时使用哪一种」这节课中我会学到什么？
利用贪心选择性质和交换论证，识别适合用贪心算法解决的问题，以及必须使用 DP 的问题。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「贪心算法与 DP：何时使用哪一种」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 贪心算法与 DP：何时使用哪一种
- 区间调度与合并
- 跳跃游戏 I 与 II
- 任务调度器与加油站