Topic 18 of 20
Dynamic Programming – 2D & Advanced
Grids, two-string DP, stock state machines, interval DP and bitmask DP.
The concept
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.
Patterns you will learn
Problems, in order
- 1
- 2
- 3
- 4TriangleMedium
Bottom-up from the last row with O(n) space.
Grid Paths (Bottom-up)Reported at: AmazonMicrosoft - 5Minimum Falling Path SumMedium
Row-to-row transitions with three parents.
Grid PathsReported at: Google - 6Maximal SquareMedium
The min-of-three-neighbours recurrence.
Grid DPReported at: MicrosoftGoogleAmazon+4 - 7
The same recurrence, used for counting.
Grid DPReported at: GoogleBloomberg - 8
The foundational two-string DP.
Two-string DP (LCS / Edit Distance)Reported at: AmazonDoorDashBloomberg - 9
Reduces directly to LCS.
Two-string DP (LCS / Edit Distance)Reported at: Amazon - 10Edit DistanceMedium
Insert, delete and replace transitions; a top Google question.
Two-string DP (LCS / Edit Distance)Reported at: AmazonMicrosoftGoogle+4 - 11Interleaving StringMedium
Two-pointer state on two strings.
Two-string DPReported at: AmazonAppleGoogle+2 - 12
LCS with the reversed string, or interval DP.
Interval DPReported at: AmazonMicrosoftApple+3 - 13
- 14
The same state machine with a fee.
State Machine DPReported at: AmazonMeta - 15
- 16
- 17
- 18
- 19
- 20
Counting subsequence matches.
Two-string DP (Counting)Reported at: AmazonGoogle - 21
The '*' transitions are a classic Hard.
Two-string DPReported at: MetaMicrosoftGoogle+6 - 22
A close cousin of regex matching.
Two-string DPReported at: MicrosoftAmazonGoogle+2 - 23
Two-transaction state machine.
State Machine DPReported at: AmazonAppleUber - 24
Generalised to k transactions.
State Machine DPReported at: AmazonAppleGoogle+1 - 25Burst BalloonsHard
Choose the *last* balloon to burst; the defining interval DP.
Interval DPReported at: GoogleMicrosoftApple+3 - 26
- 27
Palindrome table plus a minimum-cuts DP.
Interval DP + 1D DPReported at: Amazon - 28Dungeon GameHard
Solve from the end because the constraint flows backward.
Grid Paths (Reverse)Reported at: AmazonUber - 29
- 30