Topic 18 of 20
Grids, two-string DP, stock state machines, interval DP and bitmask DP.
When one index is not enough to describe a subproblem, the DP state grows a second dimension. In grid DP, dp[r][c] is the answer for reaching cell (r, c), built from its neighbours. In two-string DP, dp[i][j] describes the first i characters of one string and the first j of another. That single idea powers Longest Common Subsequence, Edit Distance, Distinct Subsequences and regular-expression matching.
Some problems are best seen as a state machine: in the stock-trading series, each day you are either holding, not holding or in a cooldown, and each state transitions to the next day's states. Interval DP defines dp[l][r] over a subarray and tries every split point, as in Burst Balloons and cutting sticks. Bitmask DP encodes a set of chosen items as the bits of an integer, which makes "assign each of n ≤ 20 things" problems tractable.
Always draw the table, fill a small example by hand, and look for the direction of dependencies. It tells you the loop order and whether you can reduce memory to one or two rows.
Bottom-up from the last row with O(n) space.
Row-to-row transitions with three parents.
The min-of-three-neighbours recurrence.
The same recurrence, used for counting.
The foundational two-string DP.
Reduces directly to LCS.
Insert, delete and replace transitions; a top Google question.
Two-pointer state on two strings.
LCS with the reversed string, or interval DP.
The same state machine with a fee.
Counting subsequence matches.
The '*' transitions are a classic Hard.
A close cousin of regex matching.
Two-transaction state machine.
Generalised to k transactions.
Choose the *last* balloon to burst; the defining interval DP.
Palindrome table plus a minimum-cuts DP.
Solve from the end because the constraint flows backward.