Dynamic Programming: Optimal Substructure and Overlapping Subproblems
When a problem's best answer is built from best answers to smaller versions, and the same smaller versions keep reappearing, storing each answer once turns an exponential recursion into a polynomial one. The two conditions are what decide whether the method applies.
What a learner can do afterwards
- Turn a naive recursive Fibonacci into a memoised one and count the calls saved
- State the subproblem and the recurrence before writing any code
- Say which of the two conditions fails for a problem where the method does not apply
1 · Read
Some problems hide smaller copies of themselves inside. When the best answer to the whole problem is built from best answers to those smaller versions, the problem has optimal substructure. Your first move is always to name the smaller version, called the subproblem, and the rule that combines them, called the recurrence. The smallest version you answer directly is the base case. For Fibonacci the subproblem is fib(k) for k below n, with fib(k) = fib(k-1) + fib(k-2).
Watch naive fib(20) run and it makes over 20,000 calls, because it recomputes the same small values again and again. The memoised version computes each of fib(0) through fib(20) exactly once, which is 21 values, each in constant extra work. Same recurrence, same answers, hugely less work, because no value is ever computed twice.
The second condition is overlap: the same smaller versions must keep reappearing. When they do, you store each answer the first time you compute it and reuse it later, which is called memoising. Moving a stack of rings never repeats a smaller move, since each move happens once, so storing answers there saves nothing.
Before any code, ask two questions. One, is the best answer built from best answers to smaller versions. Two, do those smaller versions repeat. Mergesort fails the second, since its pieces are all distinct. The longest simple path fails the first, since reusing vertices breaks the buildup. For rod-cutting, state the subproblem and recurrence first, then memoise.
Name the subproblem and recurrence, check both conditions, and store each repeated answer once.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.