Greedy vs Dynamic Programming#
Interviewers often want you to justify why greedy works or why DP is required. This page clarifies the decision; problems live in Greedy and DP.
Quick decision#
flowchart TD
A[Optimization problem] --> B{Greedy choice + proof?}
B -->|Yes - exchange argument or matroid| C[Greedy]
B -->|No| D{Optimal substructure + overlapping subproblems?}
D -->|Yes| E[DP]
D -->|No| F[Try math / binary search / graph]Greedy#
Idea: At each step, take the locally best choice; never revisit.
Requires proof (in interview, state it briefly):
- Exchange argument — swapping greedy choice into any optimal solution doesn't worsen it.
- Staying ahead — greedy is never worse than optimal after k steps.
- Matroid (rare to name) — interval scheduling, MST.
| Problem | Greedy choice | Pattern |
|---|---|---|
| Activity selection | Earliest finish time | Intervals |
| Jump Game I | Max reachable index | Greedy |
| Assign cookies | Smallest sufficient cookie | Greedy + sort |
| Huffman coding | Merge two smallest | Heap / greedy |
| Minimum arrows | Sort by end, shoot at end | Intervals |
Complexity: Usually O(n log n) from sorting + O(n) scan.
Dynamic programming#
Idea: Try all meaningful states; reuse optimal subsolutions.
Use when:
- Greedy fails (counterexample exists) — e.g. 0/1 knapsack vs fractional knapsack.
- Need count of ways or min/max with constraints that break greedy.
- Two sequences or two dimensions (LCS, edit distance).
| Problem | Why not greedy? | DP state |
|---|---|---|
| 0/1 Knapsack | Can't take fractions | dp[i][w] |
| Coin Change (min coins) | Greedy fails for arbitrary denominations | dp[amount] |
| Longest common subsequence | Must consider skip/match both strings | dp[i][j] |
| Stock with cooldown | Past choices constrain future | state machine |
Side-by-side examples#
Interval scheduling — Greedy wins#
Non-overlapping intervals, maximize count → sort by end time, take next compatible.
Proof: earliest finish leaves most room. See LC 435.
0/1 Knapsack — DP required#
Items have weight and value; each item once. Greedy by value/weight ratio fails on small counterexamples.
See DP knapsack.
Jump Game I vs II#
| Variant | Approach | Why |
|---|---|---|
| Can reach end? (LC 55) | Greedy max reach | One pass |
| Min jumps (LC 45) | Greedy layers or BFS | Different state — not simple greedy on same metric |
Both in Greedy.
What to say in interviews#
Choosing greedy:
" I'll sort by finish time and greedily pick the next compatible interval — exchange argument shows we can always swap an optimal first pick for the earliest-finishing one without reducing count."
Choosing DP:
" Subproblems overlap: whether we include item i depends on capacity w, and both recur. State dp[i][w] = max value using first i items at capacity w."
When unsure:
Try greedy → state proof → if stuck, write small counterexample → switch to DP.