Kapan dynamic programming diterapake versus greedy?

Question

Accepted Answer

Loro DP lan greedy butuh **optimal substructure**. Prabedane: **greedy** uga merlu **greedy-choice property** (local optimum iku global optimum), dene **DP** perlu nalika sampeyan kudu nimbang **pirang-pirang pilihan lan overlapping subproblems**.

## Apa pentinge

```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
```

## Contrast klasik: coin change

```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 nutup maneh sa pilihan siji; DP njajal kabehe lan nggo sing paling apik.

## Kapan saben-sabene diterapake

- **Greedy:** interval scheduling, Huffman, Dijkstra, MST — greedy-choice property wis kabuktekake.
- **DP:** knapsack, edit distance, coin change umum — pilihan-pilahe padha makresepan.

## Karangkene

Greedy biasane O(n log n); DP ngganti luwih akeh wektu/memory (asring O(n·m)) kanggo kabeneren.

## Pitfalls

Manggo greedy tanpa buktekake sipate dadi **jawaban salah** sing lulus test cilik. Yen ragu, ambil DP utawa verifikasi greedy karo brute force.

## Apa pentinge

Pilih greedy nalika valid ngirit wektu banget; pilih nalika ora valid gawe bug dadi senyep.

Karuwan paradigma mana sing cocok — lan iso buktekake — iku kakarone level senior.

Cegahe over-engineering karo DP lan under-delivering karo greedy choice sing ora kuwat.