动态规划何时适用，而不是贪心算法？

Question

动态规划何时适用，而不是贪心算法？

IT Interview Practice · Accepted Answer

DP 和贪心都需要**最优子结构**。区别是：**贪心**还需要**贪心选择性质**（局部最优就是全局最优），而**DP** 是在你必须考虑**多个选择和重叠子问题**时需要的。

## 区别

```text
Optimal substructure?  -- both need this
  + greedy-choice property holds?  -> GREEDY (fast, one pass of choices)
  + must compare many sub-solutions / they overlap?  -> DYNAMIC PROGRAMMING
```

## 经典对比：硬币兑换

```python
# Greedy FAILS for coins {1,3,4}, amount 6 -> 4+1+1 (3 coins)
# DP finds the true optimum: 3+3 (2 coins)
def min_coins(amount, coins):
    INF = float('inf')
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)  # try every coin
    return dp[amount]

min_coins(6, [1, 3, 4])               # -> 2
```

贪心承诺一个选择；DP 探索所有并保留最好的。

## 何时各自适用

- **贪心：** 区间调度、Huffman、Dijkstra、MST — 已证明贪心选择性质。
- **DP：** 背包、编辑距离、通用硬币兑换 — 选择相互关联。

## 复杂度

贪心通常是 O(n log n)；DP 以更多时间/空间（通常 O(n·m)）换取正确性。

## 陷阱

未经证明就使用贪心会导致**错误答案**，这些答案可能通过小型测试。有疑问时，请使用 DP 或针对暴力法验证贪心。

## 为什么这很重要

选择有效的贪心可以节省大量时间；在无效时选择贪心会产生隐蔽的漏洞。

知道哪种范式适用——并能够证明它——是高级水平的区别。

它防止了既过度工程化的 DP 和不完善的贪心选择造成的交付不足。

区别

经典对比：硬币兑换

相关问题

何时各自适用

复杂度

陷阱

为什么这很重要