DP vs Greedy -- When to Use Which

Quick Revisit

• Reach for this when you can solve the problem but are unsure whether to use DP or greedy.
• The real rule is: do not trust a greedy hunch without a proof. If you can sketch an exchange argument quickly, go greedy. Otherwise default to DP — but watch for cases where the DP state space is too large and a non-exchange greedy proof (matroid theory, structural argument) is the only viable path.
• The deeper proof obligation is discussed in the Greedy chapter.
• See also: Data Structure Selection Guide.

Quick decision guide. Read this when you can solve the problem but aren't sure whether to reach for DP or greedy.

---

Contents

• The One-Minute Decision Tree
• Side-by-Side Comparison
• The Exchange Argument (Greedy Proof Template)
• Classic Examples
• Common Mistakes in Choosing
• Insight Gaps
• Practical Tips
• Self-Test
• Cross-References
• What Would You Do If...?
• The Mistake That Teaches
• Recap

---

The One-Minute Decision Tree

Does a locally optimal choice always lead to a globally optimal solution?
  |
  +-- YES  -->  Can you PROVE it (exchange argument)?
  |               |
  |               +-- YES  -->  GREEDY   (faster, simpler)
  |               +-- NO   -->  DP       (greedy hunch might be wrong)
  |
  +-- NO / UNSURE  -->  Does the problem have:
                          (1) Overlapping subproblems?
                          (2) Optimal substructure?
                            |
                            +-- Both YES  -->  DP
                            +-- Only (2)  -->  Divide & Conquer
                            +-- Neither   -->  Brute force / other

---

Side-by-Side Comparison

Aspect	Greedy	DP
Core idea	Make the best local choice, never reconsider	Try all choices, remember and reuse results
Proof obligation	Exchange argument or matroid theory	Bellman's principle (optimal substructure)
Time	Usually $O(n\log n)$ (sort + scan)	$O(\text{states}\times \text{transitions})$
Space	$O(1)$-$O(n)$	$O(\text{states})$ (can be large)
Implementation	Short, elegant	Longer, table-filling or memoization
Debugging	Hard -- wrong greedy gives wrong answer silently	Easier -- print the DP table to inspect
When it fails	Greedy-choice property doesn't hold	State space too large, or no overlapping subproblems

---

The Exchange Argument (Greedy Proof Template)

The exchange argument is the most common greedy proof, but not the only one. Other valid proofs include matroid arguments (where the greedy structure is theoretical), structural induction (e.g., MST cut/cycle property), and "stays ahead" arguments. The shared obligation is the same: prove it before you trust it.

The exchange argument template:

1. Let $O$ be an optimal solution that differs from greedy solution $G$.
2. Find the first place where $O$ and $G$ differ.
3. Show you can swap $O$'s choice for $G$'s choice without worsening the cost.
4. Repeat -- each swap brings $O$ closer to $G$ without losing optimality.
5. Conclude: $G$ is also optimal.

If you cannot construct step 3, the greedy is likely wrong. Fall back to DP — unless the DP state space is too large, in which case look for a non-exchange greedy proof or a problem-specific structural argument.

---

Quick Decision Table -- Greedy vs DP Pitfalls

These 5 concrete problems demonstrate where choosing the wrong approach gives Wrong Answer (WA), not just suboptimal performance:

#	Problem	Wrong Choice	What Happens	Correct Approach
1	0/1 Knapsack (items have weight + value, pick subset <= capacity)	Greedy: pick highest value/weight ratio first	Fails on items=[(v=6,w=3),(v=5,w=2),(v=5,w=2)], cap=4. Greedy takes (6,3) for total 6; optimal takes both (5,2)s for total 10.	DP: dp[j] = max value using capacity <= j
2	Coin Change (denominations {1,3,4}, target 6)	Greedy: pick largest coin first	Greedy picks 4+1+1 = 3 coins. Optimal is 3+3 = 2 coins. Largest-first forecloses the better path.	DP: dp[x] = min coins to make amount x
3	Longest Increasing Subsequence	Greedy: always extend with the smallest available next element	Greedy can commit to a locally good element that blocks a longer subsequence. E.g., [3,1,2,4] -- greedy starting with 3 gives [3,4] length 2, but [1,2,4] has length 3.	DP: dp[i] = length of LIS ending at i, or patience sorting O(n log n)
4	Weighted Job Scheduling (jobs have start, end, profit)	Greedy: pick highest-profit job first	A high-profit job may block many smaller jobs whose combined profit exceeds it. E.g., one job worth 10 spanning the whole day vs three non-overlapping jobs worth 5 each = 15.	DP after sorting by end time: dp[i] = max(dp[i-1], dp[latest_compatible] + profit[i])
5	Partition Equal Subset Sum (split array into two halves with equal sum)	Greedy: alternately assign largest remaining element to the lighter half	Fails on [7,5,5,3]. Greedy: assign 7->A(7), 5->B(5), 5->A(12), 3->B(8). Sums 12!=8. Optimal: {7,3} and {5,5} both sum to 10.	DP (subset sum): dp[j] = can we achieve sum j from available items?

Pattern: Greedy gives WA when choices interact -- picking one item affects which future items are available or beneficial. If you can't prove the greedy-choice property via exchange argument, default to DP.

---

Classic Examples

Greedy wins

Problem	Why greedy works	Key
Activity selection	Earliest finish leaves most room	Sort by end time
Fractional knapsack	Best value/weight ratio first	Sort by ratio
Huffman coding	Merging smallest frequencies first	Priority queue
Minimum spanning tree	Cheapest safe edge is always correct	Cut property

DP wins (greedy fails)

Problem	Why greedy fails	DP state
0/1 Knapsack	Best ratio item may not fit optimally	$dp[i][w]$
Longest Common Subsequence	No local criterion for matching	$dp[i][j]$
Matrix chain multiplication	No way to pick optimal split locally	$dp[i][j]$
Coin change (arbitrary denominations)	Largest coin first can overshoot	$dp[amount]$

Tricky cases (looks greedy, needs DP)

• Coin change with denominations {1, 3, 4}: Greedy picks 4+1+1 = 3 coins for 6, but 3+3 = 2 coins. The greedy-choice property fails because denominations aren't "nice."
• Weighted job scheduling: Unweighted -> greedy (earliest finish). Weighted -> DP (must consider all compatible subsets).

---

Common Mistakes in Choosing

Integrated from reflection notes

Trap: "If greedy passes the samples, it's probably correct."

Samples illustrate the problem, not distinguish approaches. A wrong greedy that happens to work on samples will fail on adversarial judge tests.

  Sample Input:                 Adversarial Input:
  items = [(v=6,w=3),           items = [(v=6,w=3),
           (v=5,w=2)]                    (v=5,w=2),
  cap = 4                                (v=5,w=2)]
                                cap = 4
  Greedy (best ratio first):
    take (5,2) ratio=2.5        take (6,3) ratio=2.0
    take (6,3)? NO, w=3>1       take (5,2)? NO, w=2>1
    total = 5                   total = 6
                                
  Optimal:                      Optimal:
    take (6,3) alone = 6        take (5,2)+(5,2) = 10  <-- greedy FAILS
    Greedy gets 5, not 6

Trap: "This looks like knapsack, so it needs DP."

  +-------------------+------------------+------------------+
  | Problem variant   | Approach         | Why              |
  +-------------------+------------------+------------------+
  | 0-1 Knapsack      | DP               | Choices interact |
  | Fractional Knap.  | GREEDY           | Can take fracs   |
  | Activity Select.  | GREEDY           | Earliest finish  |
  | Weighted Jobs     | DP               | Weights matter   |
  +-------------------+------------------+------------------+
  
  Surface appearance != structure.
  Check: do earlier choices constrain later choices?

Trap: "The greedy choice is obvious once you see it."

In hindsight, greedy looks obvious. During solving, many wrong greedy choices also look obvious. The "obvious" feeling is unreliable. Only formal proofs (exchange argument) and empirical testing (counterexamples) are reliable.

Trap: "DP can be optimized to run in the same time as greedy."

Not always. A $O(n^2)$ DP cannot always become $O(n\log n)$ -- that depends on the transition structure. Verify DP can be fast enough before committing.

Trap: "If the time limit is tight, greedy must be the intended approach."

A tight time limit means the intended solution is fast -- it does not mean greedy is correct. Many DP solutions run in $O(n\log n)$ with optimizations (convex hull trick, divide-and-conquer DP). A wrong greedy that runs in $O(n\log n)$ is still wrong.

  TIME LIMIT vs CORRECTNESS (decision flowchart):

       Problem has tight TL
              |
              v
     +-----------------+
     | Can I prove the |
     | greedy correct? |
     +---+---------+---+
        YES        NO
         |          |
         v          v
   +----------+  +----------------------+
   | Use      |  | Look for fast DP:    |
   | greedy   |  | - O(n log n) tricks  |
   +----------+  |   (CHT, D&C opt.)   |
                 | - Monotone queue     |
                 | - Knuth's opt.       |
                 +----------------------+

  Tight TL != greedy.  Tight TL = fast algorithm.

Trap: "DP state design is mechanical -- just look at the constraints."

Constraints tell you the size of each dimension, but not which dimensions you need. Choosing the wrong state definition produces a DP that is either incorrect (missing information) or too slow (carrying unnecessary information).

  WRONG mental model:          CORRECT mental model:

  "n <= 1000, W <= 1000           "What INFORMATION do I need
   -> dp[n][W], done."            to make optimal future
                                 decisions?"
  +------------------------+          |
  | Leads to copying       |          v
  | standard templates     |    +------------------+
  | that may not fit the   |    | Only that info   |
  | actual problem.        |    | becomes a state  |
  +------------------------+    | dimension.       |
                                +------------------+

  Example: scheduling jobs with deadlines + profits
    WRONG state:  dp[i] = max profit using first i jobs
    (missing info: when does my schedule become free?)
    RIGHT state:  dp[i][t] = max profit, first i jobs, free at time t

---

Insight Gaps

Integrated from reflection notes

Greedy proofs are a skill, not a heuristic. Practice writing exchange argument proofs for 10-15 problems to build pattern recognition.

The spectrum between greedy and DP:

  Pure Greedy          Greedy-Reducible           Pure DP
  <------------------------------------------------------------>
  |                         |                              |
  One specific choice   A CLASS of choices             All choices
  is always optimal     is always optimal              must be tried
  |                         |                              |
  Activity selection    Sort by deadline,              0-1 Knapsack
  Huffman coding        then DP on reduced set         LCS, Edit dist
  
  Many real problems live in the MIDDLE:
  greedy insight reduces the state space, DP solves the rest.

DP and greedy as complementary tools:

  Problem: Weighted Job Scheduling
  
  Step 1 (Greedy insight): Sort jobs by end time
         +--+  +----+  +--+  +------+
    -----| A|--|  B |--| C|--|  D   |------> time
         +--+  +----+  +--+  +------+
  
  Step 2 (DP): dp[i] = max profit considering first i jobs
         dp[i] = max(dp[i-1],              // skip job i
                     dp[latest_compat] + w) // take job i
  
  Neither pure greedy nor pure DP alone -- BOTH cooperate.

Key diagnostic question:

  "Do earlier choices constrain later choices?"
       |                          |
      YES                        NO
       |                          |
       v                          v
      DP                        GREEDY
  (choices interact)      (independent or locally optimal)

What the Code Won't Teach You

Greedy proofs are a learnable skill. Writing exchange argument proofs for 10-15 problems builds the pattern recognition that makes future greedy identification fast. It's not innate -- it's practice.

Many real problems live in the middle of the spectrum. Not purely greedy, not purely DP. A greedy insight reduces the state space, and DP solves the reduced subproblem. Recognizing this hybrid pattern is a key skill beyond 1600.

The counterexample discipline saves contests. Before coding any greedy, spend 3-5 minutes trying to break it. Construct adversarial inputs: many choices with similar keys, inputs designed to make greedy commit to a bad early path. If you can't break it, the greedy might be correct.

  THE COUNTEREXAMPLE CONSTRUCTION CHECKLIST:

  +---------------------------------------------+
  | Proposed greedy rule: "always take X first" |
  +---------------------------------------------+
  | Try to break it:                            |
  |                                             |
  | 1. Two options with similar X but different |
  |    long-term consequences                   |
  |                                             |
  | 2. An input where X forces a bad path that  |
  |    a different first choice avoids           |
  |                                             |
  | 3. Small n (3-5 items) where brute force    |
  |    gives a different answer than greedy      |
  |                                             |
  | Can't break it after 5 min?                 |
  | --> Write the exchange argument.            |
  | --> If argument holds, greedy is correct.   |
  +---------------------------------------------+

Recognizing "greedy-reducible" problems is the real unlock. Many 1600+ problems are neither pure greedy nor pure DP -- a greedy insight (e.g., sorting by deadline) reduces the state space, then DP finishes the job. Asking "can I eliminate choices before running DP?" is the question that bridges the two paradigms.

  GREEDY-REDUCIBLE DETECTION (decision flowchart):

  Can you prove SOME choices are always suboptimal?
  |
  +-- YES -> Eliminate those choices (sort, prune)
  |          |
  |          v
  |   Remaining problem still need DP?
  |   +-- YES -> Greedy preprocessing + DP
  |   |          (e.g., sort by deadline, then DP)
  |   +-- NO  -> Pure greedy (all choices resolved)
  |
  +-- NO --> Full DP over all choices
             (no shortcut available)

DP debugging is a transferable skill. When a DP gives WA, printing the table and tracing the optimal path backward almost always reveals the bug: a wrong base case, an off-by-one in the transition, or a missing state dimension. This "table inspection" discipline is faster than staring at the recurrence.

  DP DEBUGGING FLOWCHART:

       DP gives Wrong Answer
              |
              v
     Print the DP table
     for a small input (n <= 5)
              |
              v
     +------------------------+
     | Trace optimal path     |
     | backward through table |
     +-----------+------------+
              |
              v
     +------------------------+     +------------------+
     | Path makes sense?      |-NO->| Transition is    |
     +-----------+------------+     | wrong -- fix      |
                YES                 | recurrence       |
                 |                  +------------------+
                 v
     +------------------------+     +------------------+
     | Base cases correct?    |-NO->| Fix base cases   |
     +-----------+------------+     +------------------+
                YES
                 |
                 v
     +------------------------+     +------------------+
     | All dimensions present?|-NO->| Add missing      |
     +-----------+------------+     | state dimension  |
                YES                 +------------------+
                 |
                 v
         Check index bounds
         and loop ordering

---

Practical Tips

1. Try greedy first -- it's faster to code. Sketch the exchange argument on paper.
2. If the argument has a gap, don't force it. Switch to DP.
3. Small test cases expose bad greedy: generate all permutations / subsets for $n\le 8$ and compare greedy output to brute-force optimal.
4. "Minimum cost to do X" usually means DP. "Maximum items you can select" with independence often means greedy.
5. Hybrid: Some problems use greedy insight to reduce the state space of a DP (e.g., sorting items by deadline before running DP).

---

Self-Test

Drawn from reflection notes

Without opening any reference:

1. Write the exchange argument for activity selection (sort by end time, greedily take non-overlapping intervals). Prove it's optimal.

2. Construct a counterexample to greedy for 0-1 knapsack: "always take the highest value-to-weight ratio item." Give a specific failing instance.

3. Classify DP vs greedy (decision + one-sentence justification):

   • "Minimum coins to make amount $X$" (arbitrary denominations)
   • "Maximum non-overlapping meetings"
   • "Minimum cost to connect all cities" (MST)

4. Write the DP transition for coin change: define state, recurrence, base case.

5. Worked example -- greedy fails on coin change:

  Denominations: {1, 3, 4}    Target: 6
  
  Greedy (largest first):
  +---+---+---+---+---+---+
  | 4 |   |   |   |   |   |  Take 4  (remaining: 2)
  +---+---+---+---+---+---+
  | 4 | 1 |   |   |   |   |  Take 1  (remaining: 1)
  +---+---+---+---+---+---+
  | 4 | 1 | 1 |   |   |   |  Take 1  (remaining: 0)
  +---+---+---+---+---+---+
  Greedy uses 3 coins: {4, 1, 1}
  
  DP (optimal):
  +---+---+---+---+---+---+
  | 3 |   |   |   |   |   |  Take 3  (remaining: 3)
  +---+---+---+---+---+---+
  | 3 | 3 |   |   |   |   |  Take 3  (remaining: 0)
  +---+---+---+---+---+---+
  DP uses 2 coins: {3, 3}  <-- OPTIMAL
  
  Why greedy fails: taking 4 forecloses the 3+3 path.
  Earlier choice (4) constrains later choices --> need DP.

6. Name one problem from your practice where greedy got WA and DP was needed. What was the counterexample?

Quick self-checks:

• [ ] Can you write the exchange argument for activity selection without looking?
• [ ] Can you construct a counterexample to greedy for 0-1 knapsack on the spot?
• [ ] Can you classify DP vs greedy for coin change, interval scheduling, and MST -- with justification?
• [ ] Can you write the DP transition for coin change (state, recurrence, base case) from memory?
• [ ] Can you name one problem where greedy + DP cooperate (neither alone suffices)?
• [ ] Can you identify a "greedy-reducible" structure -- where a greedy preprocessing step shrinks the DP state space?
• [ ] Can you debug a wrong DP by printing the table for $n\le 5$ and tracing the optimal path backward?
• [ ] Can you name two DP optimizations that achieve $O(n\log n)$ (e.g., convex hull trick, D&C optimization)?
• [ ] Can you explain why a tight time limit does NOT imply greedy -- and give an example of fast DP?
• [ ] Can you design a DP state by asking "what information do I need to make optimal future decisions?" -- not just reading constraints?

  GREEDY vs DP -- PROBLEM INDICATORS AT A GLANCE:

  Almost always GREEDY:        Almost always DP:
  +----------------------+     +--------------------------+
  | "Max # of non-overlap|     | "Max total value"        |
  |  intervals"          |     |  with item weights       |
  |                      |     |                          |
  | "Min # of operations"|     | "Number of ways to       |
  |  (with structure)    |     |  achieve X"              |
  |                      |     |                          |
  | "Sort by X, greedily |     | "Min cost to transform   |
  |  process"            |     |  X into Y"               |
  |                      |     |                          |
  | Exchange argument is |     | Choices at step i        |
  | obvious              |     | constrain step i+1       |
  +----------------------+     +--------------------------+

  IN THE MIDDLE (greedy + DP):
  +----------------------------------------------+
  | Weighted job scheduling: sort by end time    |
  | (greedy), then dp[i] = max profit (DP)       |
  |                                              |
  | Knapsack with special structure: greedy to   |
  | reduce state space, then DP on what remains  |
  +----------------------------------------------+

---

Cross-References

• Greedy -- exchange argument, sorting key discovery
• 1-D DP -- state identification checklist, top-down vs bottom-up
• Knapsack DP -- classic DP-beats-greedy example
• BFS vs DFS Guide
• Problem Pattern Recognition

---

What Would You Do If...?

1. The problem asks for minimum cost -- is it greedy or DP?
2. Your greedy passes samples but you're not sure it's correct -- how do you decide whether to submit or switch to DP?
3. The problem has overlapping subproblems but also a natural greedy ordering -- which approach?

The Mistake That Teaches

Codeforces Round 791, problem C. 'Minimize total cost of operations.' You see the greedy: always pick the cheapest option. It passes 4/5 samples. You submit -- WA. The 5th sample had a case where a locally expensive choice led to globally cheaper future options. Classic DP territory disguised as greedy.

---

Recap

• Exchange argument is the test: if you can prove swapping any non-greedy choice for the greedy choice never worsens the answer, greedy is correct.
• Greedy fails when choices interact: picking one item affects which future items are available or beneficial.
• DP is the safe default: when in doubt, DP explores all possibilities. Greedy is an optimization you earn by proving correctness.
• Many real problems are hybrid: a greedy insight (e.g., sort by deadline) reduces the state space, then DP finishes the job.
• Counterexample discipline: spend 3-5 minutes trying to break your greedy before coding it.