Skip to content
Tutorials Center
My learning

Topics

Lesson 175 of 225 ยท Greedy Algorithms

Greedy vs Dynamic Programming

Compare greedy and dynamic programming in Python on the same problems: coin change, knapsack and interval scheduling. Learn when greedy fails and how to decide.

Greedy algorithms and dynamic programming attack the same family of problems: optimization over a sequence of choices. Both rely on optimal substructure, meaning the best answer is built from best answers to smaller pieces. The difference is how many pieces they look at. DP considers every option at each step and remembers the answers. Greedy commits to one option and moves on.

That makes greedy faster and simpler, but only correct when a special property holds. Pick it where it does not, and you get a confident wrong answer. This lesson solves the same problems both ways, shows greedy failing, and ends with a checklist you can run in your head.

The core difference

TEXT
            greedy                          dynamic programming
choice:     one, the "best-looking" one     all of them
memory:     little or none                  a table of subproblem answers
backtrack:  never                           implicitly, by comparing options
speed:      usually O(n) or O(n log n)      usually O(n * something)
correct:    only with the greedy-choice     whenever the problem has optimal
            property                        substructure and overlapping subproblems

Greedy needs both ingredients DP needs plus the greedy-choice property: there is always an optimal solution that contains the locally best choice. When that property is missing, greedy can make a choice that no later step can repair.

Example 1: Coin change

Make an amount with as few coins as possible.

Python Greedy and DP side by side on coin change

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For US coins the two always agree. For [1, 3, 4] and amount 6, greedy takes 4 + 1 + 1, while DP finds 3 + 3. For [1, 15, 25] and amount 30, greedy takes 25 + 1 + 1 + 1 + 1 + 1 (six coins) while 15 + 15 uses two. See coin change for the DP in full.

Which systems are safe? A coin system where greedy is optimal for every amount is called canonical. The US system is one. There is no simple one-line test, but a small program can look for a counterexample by comparing greedy and DP over a range of amounts.

Python Test whether a coin system is greedy-safe

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A search like this only proves failure (a counterexample) or gives evidence of safety up to the limit. It is a handy way to test any greedy idea: write the slow, obviously right version and compare on many small inputs.

Example 2: Knapsack, whole and fractional

We saw in greedy problems that taking items by value per weight is optimal when items can be cut. For whole items (the 0/1 knapsack) it is not.

Python Knapsack: ratio-greedy against DP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Greedy grabs the two best ratios (A and B), leaving 20 units of capacity that no remaining item fits. DP sees that dropping A for C is better overall. The leftover room is the clue: greedy cannot undo a choice, and DP compares the whole.

Example 3: One problem, two objectives

The same problem can be greedy-friendly or not depending on the objective. Take choosing non-overlapping intervals:

  • Unweighted (maximize the number of intervals): greedy by earliest finish time is optimal. See interval scheduling.
  • Weighted (maximize total weight): greedy fails, and you need DP.
TEXT
intervals (start, end, weight):
  A (0, 10, 20)    B (1, 3, 4)    C (4, 6, 4)    D (7, 9, 4)

earliest-finish greedy: B, C, D  -> 3 intervals, total weight 12
best by weight:         A alone  -> 1 interval,  total weight 20

Greedy picks the most intervals, but the one long interval A is worth more than the three short ones together. The code below compares both rules.

Python Weighted interval scheduling: greedy vs DP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Greedy by finish time optimizes the count, not the weight. Once the objective changes to weights, the greedy-choice property is gone, and DP takes over at the cost of an extra O(n log n) binary search per job.

A decision checklist

Run through these questions when you face an optimization problem.

  1. Does the problem have optimal substructure? If not, neither technique applies directly.
  2. Is there a natural order or ranking (by finish time, ratio, deadline, frequency)? If yes, greedy is a candidate.
  3. Can you argue the first greedy choice is safe? Use an exchange argument: take any optimal solution, swap in the greedy choice, and show the result is no worse.
  4. Can you break it with a tiny counterexample? Try 3 to 5 items, small numbers, ties, and a case where the best option "blocks" two decent ones.
  5. Can items be split? Fractions favor greedy. Whole items usually need DP.
  6. Are choices constrained by capacity, exact sums or counts? Exact targets (amounts, capacities, lengths) are classic DP territory.
  7. Still unsure? Write DP (or brute force) first, then test greedy against it on random small inputs.

A reliable workflow in interviews and in real code: write the slow, obviously correct version, then try a greedy rule and compare the two on thousands of small random cases. If they ever disagree, print the input and you have both a counterexample and a better understanding.

Python Stress test a greedy rule against brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reading the result: any non-zero count proves the rule wrong for 0/1 knapsack, and the first counterexample is small enough to check by hand.

Common mistakes

  • Trusting greedy because it passes the samples. Samples are usually friendly. Hunt for the input that makes the locally best choice block a better pair.
  • Mixing up objectives. Earliest finish maximizes the number of intervals, not their total weight. Change the objective and the proof no longer applies.
  • Using DP when greedy would do. Not wrong, but an O(n * W) table for fractional knapsack is wasted work next to an O(n log n) sort.
  • Assuming "canonical" coin systems. A system that works for 63 cents may fail for another amount. Test it, or use DP.
  • Skipping the proof sketch. Even a two-sentence exchange argument catches many wrong greedy rules before you code them.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does greedy need beyond optimal substructure to be correct?

    Both greedy and DP use optimal substructure. Greedy additionally requires that a locally best choice is never a mistake, which must be proved or at least tested.
  2. 2. For coins [1, 3, 4] and amount 6, how do greedy and DP compare?

    Greedy commits to the largest coin 4 and cannot undo it. DP compares all choices and finds 3 + 3.
  3. 3. Which knapsack variant can be solved correctly by sorting by value per weight?

    Cutting items lets you exchange weight at a fixed ratio, so the best ratio first is optimal. Whole items break that exchange argument.
  4. 4. Earliest-finish-time greedy is optimal for which objective?

    Finishing early leaves the most room for later intervals, which maximizes the count. With weights, one heavy long interval can beat several short ones, so DP is needed.
  5. 5. What is a good way to gain confidence in a greedy rule you cannot prove?

    A stress test against a slow but obviously correct solution finds counterexamples quickly, and the failing input shows you why the rule breaks.

Summary

  • Greedy and DP both need optimal substructure; greedy also needs the greedy-choice property, which DP does not.
  • Greedy picks one option and never reconsiders. DP tries all options and keeps a table.
  • Greedy fails on arbitrary coin systems, 0/1 knapsack and weighted interval scheduling. It succeeds on fractional knapsack, unweighted interval scheduling and canonical coin systems.
  • Test any greedy idea with tiny counterexamples and a brute-force comparison.
  • Prove greedy rules with an exchange argument: swap the greedy choice into an optimal solution and show it is no worse.
  • When in doubt, write the DP first; simplify to greedy only when you can justify it.

Next: Bit Manipulation