One-dimensional Dynamic Programming
Recursion with the answers remembered
The four-step ladder that every problem in this unit climbs, on a recurrence you have already met.
Key idea
What dynamic programming actually is
It is recursion that does not recompute. That is the entire idea, and the intimidating name has done a great deal of damage to people learning it.
If a recursion solves the same subproblem more than once, remember the answers. What remains is bookkeeping about where to store them and in what order to fill them in.
A problem you have already seen
In Unit 10 you generated every binary string of a given length with no two adjacent ones, and the counts for length 3 and length 10 were 5 and 144. Those are Fibonacci numbers, and that lesson noted that the counting version is a dynamic programming exercise rather than a search.
Here it is. Counting them without generating them is the whole point: generation is exponential and counting is linear.
Key idea
Step one: correct and slow
Write the recursion that answers the question directly, ignoring efficiency entirely. Nothing else works until this exists, because the recurrence you are about to optimize is the one this contains.
Ask: what choices are available at this position, and what does each leave behind? Here, either place a zero and continue, or place a one and be forced to place a zero next.
Why it works
Step two: remember what you computed
The recursion above recomputes the same pair of arguments many times. Store each result the first time and read it thereafter.
The key is the full set of arguments, since those are what determine the answer. Getting the key wrong, by leaving out a parameter the answer depends on, produces a memo that returns confidently wrong results, and it is the most damaging error in this unit.
Tip
Try the slow version on 40
The memoized call above answers for length 40 instantly. The unmemoized one would make hundreds of millions of calls for the same answer.
That gap is the entire value of this unit, and it comes from one dictionary. Nothing about the recurrence changed.
Key idea
Step three: turn it into a table
Memoized recursion is often the right place to stop, and it is easy to write and easy to explain. A table replaces the recursion with a loop, which avoids recursion-depth limits and is usually a little faster.
To convert, ask what the subproblems are indexed by and in what order they can be filled so that everything a cell needs is already present. Here the index is the length and the order is small to large.
Key idea
Step four: keep only what the table uses
Look at which cells the loop actually reads. Here every line reads only the previous index, so the whole array is unnecessary and two variables suffice.
This is the last step and it is optional. Do it when space matters or when an interviewer asks. Doing it first, before the table is correct, is how people end up with two variables and no idea which is which.
Gotcha
Assign the new values simultaneously
zero, one = zero + one, zero evaluates the whole right side before binding either name, so one receives the old zero. Writing the two assignments on separate lines would overwrite zero first and feed the new value into one.
This is the same read-before-overwrite discipline as the linked list unit and the prefix sweeps. When two values update from each other, either use a simultaneous assignment or save one explicitly.
Tip
Which step to actually deliver
In an interview, get to step two and say the rest. A working memoized recursion with its complexity stated is a complete answer, and offering that you could convert it to a table and then to constant space usually satisfies the follow-up without writing it.
Jumping straight to step four is the common failure. It produces code that is right or wrong with no way for either of you to tell which, and it skips the part being assessed, which is the derivation.
Predict the output: a memo key that loses a parameter
This memoizes on the length alone, ignoring the other parameter the answer depends on. Type the two values it prints.
Climb the ladder
One recurrence, three ways. ways_slow counts sequences of 1s and 3s summing to n, by plain recursion. ways_memo does the same with memory. ways_rolling does it with a fixed number of variables. All three must agree.
Tests
print([ways_slow(n) for n in range(7)]) print([ways_memo(n) for n in range(7)]) print([ways_rolling(n) for n in range(7)]) print(ways_memo(30) == ways_rolling(30), ways_rolling(30))
Output
Run the tests when you are ready.
Climbing Stairs
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Min Cost Climbing Stairs
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.