P-5.5 Greedy Choices and Dynamic Programming
You can tell when a locally best choice is provably globally best, and turn a recursive solution with repeated subproblems into a memoised or tabulated one.
These two techniques are usually taught together because they answer the same question differently. A greedy algorithm takes the best-looking step and needs a proof that this is safe; dynamic programming considers every option but never recomputes anything. The mistake that costs the most marks and the most production bugs is applying a greedy rule to a problem that does not support one, because it produces plausible wrong answers rather than obvious failures.
Work through these
A greedy algorithm, and the proof it always needs
Taking the locally best option is only correct when an exchange argument shows no better solution is lost by it. Without that argument you have a heuristic, which is a different thing worth saying out loud.
Algorithms · ReferenceA problem where greed works and one where it does not
Scheduling by earliest finishing time is provably optimal; making change greedily fails for some coin systems. Working both is what builds the instinct for telling them apart.
Overlapping subproblems: the same recursion computed again and again
Naive recursive solutions often solve identical subproblems an exponential number of times. Spotting that repetition is the trigger for everything in the rest of this topic.
Memoisation: keep the recursion, remember the answers
Storing each result the first time it is computed turns exponential work into work proportional to the number of distinct subproblems. The code barely changes, which is what makes this the easier of the two forms.
Tabulation: fill a table in an order that never looks forward
Working bottom up removes the recursion entirely and makes the memory use obvious, which often allows keeping only the last row or two. Getting the fill order right is the whole design step.
Sign in to keep your progress.
Free resources
Links last checked 31 Aug 2026.
Stuck here?
Ask a mentor. A real person answers, and they can see exactly which topic you're on. Usually within a couple of working days.
Checking your session…
Topics shown in module order.