動的計画法とGreedyアルゴリズムはいつ適用されますか？

Question

IT Interview Practice · Accepted Answer

DP と Greedy の両方が**最適部分構造**を必要とします。違いは：**Greedy** には**貪欲選択性**（局所最適解が大域最適解である）も必要ですが、**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
```

Greedy は1つの選択肢に確定し、DP はすべてを探索して最適なものを保持します。

## 各アルゴリズムが適用される場合

- **Greedy:** 区間スケジューリング、Huffman、Dijkstra、最小全域木 — 貪欲選択性が証明されている。
- **DP:** ナップサック問題、編集距離、一般的なコイン両替 — 選択肢が相互作用する。

## 計算量

Greedy は通常 O(n log n)；DP はより多くの時間/空間（しばしば O(n·m)）と引き換えに正確性を得ます。

## 落とし穴

Greedy の性質を証明せずに使用すると、小さいテストには合格する**間違った答え**が生じます。疑わしい場合は、DP を選択するか、Greedy をブルートフォースと検証してください。

## なぜ重要なのか

Greedy が有効な場合にそれを選択すると、膨大な時間を節約できます。そうでない場合に選択すると、静かなバグが発生します。

どのパラダイムが適合するか知ること — そしてそれを証明できること — はシニアレベルの区別です。

DP でのオーバーエンジニアリング、および根拠のない Greedy 選択によるアンダーデリバリーの両方を防ぎます。

なぜ重要なのか

古典的な対比：コイン両替

各アルゴリズムが適用される場合

計算量

落とし穴

なぜ重要なのか

関連する質問