Funcognito — Explore and learn anything, you got this!

P-5.5 Greedy Choices and Dynamic Programming

Standard algorithm design techniques, as in Erickson — written September 2026

What this is and why it exists

These two techniques are taught together because they answer the same question in opposite ways.

A greedy algorithm takes the best-looking step, and needs a proof that doing so is safe. Dynamic programming considers every option, and never recomputes anything.

One mistake costs more than any other here, in exams and in production alike. Applying a greedy rule to a problem that does not support one. It produces plausible wrong answers rather than obvious failures, which is the worst kind of wrong.

The vocabulary

  • Greedy choice — taking the locally best option at each step.
  • Exchange argument — a proof that the greedy choice loses no better solution.
  • Heuristic — a rule that usually works and is not proved to.
  • Subproblem — a smaller instance of the same problem.
  • Overlapping subproblems — the same subproblem arising many times.
  • Memoisation — recording each subproblem's answer the first time.
  • Tabulation — filling a table bottom up, with no recursion.

The mental model

A greedy algorithm is only correct when you can show that the locally best option loses nothing. The standard tool is an exchange argument: take any optimal solution, swap in the greedy choice, and show the result is no worse. Without an argument of that kind you do not have an algorithm, you have a heuristic. That is a perfectly respectable thing to have, and it is worth saying out loud rather than letting the code imply otherwise.

Work one of each to build the instinct. Scheduling by earliest finishing time is provably optimal, and the exchange argument is short. Making change greedily is optimal for some coin systems and wrong for others. The failure is quiet: a valid set of coins that is not the fewest. Doing both is what teaches you to distrust the feeling that greed must work here.

Dynamic programming starts from a different observation. Naive recursive solutions often solve the same subproblem an enormous number of times. Spotting that repetition is the trigger for everything else. If your recursion tree contains the same call over and over, you have found the entry point.

Memoisation is the gentle answer. Keep the recursion, and store each result the first time it is computed. Exponential work becomes work proportional to the number of *distinct* subproblems. The code barely changes, which is why this is the form to reach for first.

Tabulation removes the recursion entirely. Fill a table bottom up, in an order that never needs a value it has not computed yet. Getting that fill order right is the whole design step. The reward, beyond speed, is that the memory use becomes plain to see. Often only the last row or two is ever needed, and the rest can be thrown away.

What you should now be able to explain or do

State what a greedy algorithm needs before it can be called correct. Give an exchange argument for a problem where greed works. Give a problem where greed fails and describe how it fails. Spot overlapping subproblems in a recursion. Add memoisation without restructuring the code. Convert to a table, choose a fill order, and reduce the memory.

Check yourself

A proof, usually an exchange argument, that taking the locally best step loses no better solution.

It returns a plausible answer rather than failing. Making change greedily gives valid coins that are not the fewest, and nothing reports it.

Noticing that a recursion solves the same subproblem repeatedly. That repetition is what there is to eliminate.

The work drops from exponential to proportional to the number of distinct subproblems. The structure of the code barely changes.

Choosing a fill order that never needs a value not yet computed. Everything else follows, including seeing which rows can be discarded.

Go deeper

Back to Greedy Choices and Dynamic Programming: work through the checklist