The idea
Outside the textbook problems there is no formula to recall. Ask: “what do I need to know about the past to make the next decision?” That is the state.
Typical answers: the last choice made (so the next one can differ), an interval [l, r] of a string (palindromes), or both dimensions of a rectangle being cut.
Interval and rectangle DPs are filled from small to large: by length, or by width and height.
Sample problem
198. House Robber ↗ Medium
Houses in a row hold the given amounts of money. Robbing two adjacent houses sets off the alarm. Return the most money that can be taken.
nums = [2,7,9,3,1] output = 12 (2 + 9 + 1)
Why the solution works
No formula is given here; the state has to be invented. Ask what a decision about house i needs to know about the past: only the best total so far, and the best total that leaves house i−1 alone.
Let f[i] be the best from the first i houses. For house i there are two choices: skip it, keeping f[i−1]; or rob it, which rules out house i−1 and gives f[i−2] + nums[i−1].
The constraint “not two neighbours” is absorbed by reaching back two states instead of one.
Complexity: O(n) time and memory.
Watch out
- If a transition needs information the state does not hold, add a dimension for it.
- If the state holds more than the future depends on, the table is bigger and slower than necessary.
- For interval DP, loop over the length first so shorter intervals are ready.