Two-dimensional Dynamic Programming
Retrieval: naming the second dimension
Two problems rebuilt cold, plus the question that identifies what the second index should be.
Key idea
Four answers cover almost everything
The second index is a position in a second input, when the problem compares or combines two sequences. That is the most common by far.
It is a mode, when the available choices depend on what happened recently.
It is a quantity, such as a remaining budget or a running total, when the constraint is arithmetic rather than positional.
It is the other end of a range, when what an element is worth depends on its current neighbors.
Tip
And always check whether you need it
Before committing to two dimensions, check whether one index is implied by the other. The interleaving problem looked three-dimensional and was two, for exactly that reason.
Then check whether the table can be collapsed to a row or a few variables. Both checks cost a minute and one of them frequently pays.
What is the second index here?
You may make at most k transactions, each a buy followed by a later sell, and want the maximum profit over a price series. What should the two dimensions be?
Longest Common Subsequence, 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.
Longest Increasing Subsequence, 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.