One-dimensional Dynamic Programming
Retrieval: naming the state
Two problems rebuilt cold, plus the three questions that produce a dynamic programming solution.
Key idea
Answer these in order, in writing
What is a subproblem, and what exactly does its answer mean? Write it as a full sentence. Almost every wrong solution in this unit is a correct recurrence over a state that means something slightly different from what its author believed.
How does a subproblem relate to smaller ones? That is the recurrence, and it is one line per available choice.
What is the smallest case, and what is its answer? Usually the identity of whatever operation the recurrence uses: zero for a sum, one for a count, True for an and-chain, infinity for a minimum.
Tip
Signals that a problem is this family
The question asks for a count, a maximum, a minimum, or a yes-or-no over a huge number of arrangements, and the constraints are far too large to enumerate them.
There is a sequence of decisions, and a decision made now restricts what is available later.
A brute-force recursion is easy to write and obviously recomputes.
Gotcha
And signals that it is not
A local choice provably cannot be revisited, which usually means greedy and is the subject of Unit 16.
The answer depends on a contiguous stretch with a condition that behaves monotonically, which is a sliding window.
Reaching for a table is a common overreach on problems that have a one-pass answer. Ask whether a single running value suffices before building anything.
Which state works?
Reconsider the take-or-skip problem you solved earlier in this unit, choosing values with no two adjacent. Which state definition leads to a correct recurrence?
Coin Change, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.
Alien Dictionary, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.