2-D Dynamic Programming
When the state needs two numbers — a position in a grid, or a position in each of two strings — the DP table becomes a rectangle. You fill it cell by cell, each cell from its neighbours that are already filled.
After this topic: You can define dp[i][j] in a sentence, fill the table in the right order, and trim it to one row when possible.
Do these first: Graphs, 1-D Dynamic Programming
Step 1 · Read the lesson
Grids, two strings and ranges: when a subproblem needs two numbers, fill a table cell by cell.
Step 2 · Solve the problems in order
Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.
- 1.Unique PathsMedium
You can only reach a cell from the one above or the one to its left.
dp[r][c] = dp[r−1][c] + dp[r][c−1] with the first row and column all 1; one row of memory is enough.
Target: O(m·n) time, O(n) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func uniquePaths(m int, n int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the 2-D Dynamic Programming lesson page.
// UniquePaths: robot moves right or down on an m×n grid. // dp[c] holds the ways to reach column c of the current row; it is updated row by row in one slice. func UniquePaths(m, n int) int { dp := make([]int, n) for c := range dp { dp[c] = 1 // top row: only one way to reach each cell } for r := 1; r < m; r++ { for c := 1; c < n; c++ { dp[c] += dp[c-1] // from above (old dp[c]) + from the left (new dp[c-1]) } } return dp[n-1] } - 2.Longest Common SubsequenceMedium
Compare the last characters of the two prefixes. If equal, they extend the answer; if not, one of them is dropped.
dp[i][j] = dp[i−1][j−1] + 1 if a[i−1]==b[j−1], else max(dp[i−1][j], dp[i][j−1]).
Target: O(m·n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func longestCommonSubsequence(text1 string, text2 string) intTested with go test. Try it yourself first, then compare. It is explained step by step on the 2-D Dynamic Programming lesson page.
// LongestCommonSubsequence. // State: dp[i][j] = LCS length of a[:i] and b[:j]. Row 0 and column 0 are the empty-prefix base cases. func LongestCommonSubsequence(a, b string) int { dp := make([][]int, len(a)+1) for i := range dp { dp[i] = make([]int, len(b)+1) } for i := 1; i <= len(a); i++ { for j := 1; j <= len(b); j++ { if a[i-1] == b[j-1] { dp[i][j] = dp[i-1][j-1] + 1 // match: extend the diagonal } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // drop one character } } } return dp[len(a)][len(b)] } - 3.Best Time to Buy and Sell Stock with CooldownMedium
On each day you are in one of a few states: holding, just sold (cooling), or resting.
State machine: hold = max(hold, rest − price); sold = hold + price; rest = max(rest, previous sold). Iterate over the days.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func maxProfit(prices []int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the 2-D Dynamic Programming lesson page.
// MaxProfitCooldown: unlimited trades, but you must rest one day after selling. // Three states per day: holding a stock, just sold (cooling down), or resting with nothing. func MaxProfitCooldown(prices []int) int { hold, sold, rest := -1<<31, 0, 0 for _, p := range prices { prevSold := sold sold = hold + p hold = max(hold, rest-p) rest = max(rest, prevSold) } return max(sold, rest) } - 4.Coin Change IIMedium
You count combinations, not orderings. Process one coin type at a time.
ways[0]=1; for each coin, for a from coin to amount: ways[a] += ways[a−coin].
Target: O(amount · coins) time, O(amount) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func change(amount int, coins []int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the 2-D Dynamic Programming lesson page.
// Change: number of COMBINATIONS of coins that make amount. // Coins are the OUTER loop, so each combination is counted once, in a fixed coin order. func Change(amount int, coins []int) int { ways := make([]int, amount+1) ways[0] = 1 for _, coin := range coins { for a := coin; a <= amount; a++ { ways[a] += ways[a-coin] } } return ways[amount] } - 5.Target SumMedium
Choosing + or − for every number splits the numbers into two groups. What must one group sum to?
Either memoize (index, total) or convert to "count subsets with sum (S + target)/2" using a 1-D knapsack count.
Target: O(n · sum) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func findTargetSumWays(nums []int, target int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the 2-D Dynamic Programming lesson page.
// FindTargetSumWays: choose + or - for every number so the total is target. // The + group P and - group N satisfy P - N = target and P + N = sum, so P = (sum + target) / 2: // count subsets that add up to P. func FindTargetSumWays(nums []int, target int) int { sum := 0 for _, n := range nums { sum += n } if (sum+target)%2 != 0 || sum+target < 0 || target > sum || -target > sum { return 0 } want := (sum + target) / 2 ways := make([]int, want+1) ways[0] = 1 for _, n := range nums { for s := want; s >= n; s-- { // descending: each number used at most once ways[s] += ways[s-n] } } return ways[want] } - 6.Interleaving StringMedium
After using i characters of s1 and j of s2, the next character of s3 is at index i+j.
dp[i][j] = (dp[i−1][j] and s1[i−1]==s3[i+j−1]) or (dp[i][j−1] and s2[j−1]==s3[i+j−1]).
Target: O(m·n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func isInterleave(s1 string, s2 string, s3 string) boolTested with go test. Try it yourself first, then compare. It is explained step by step on the 2-D Dynamic Programming lesson page.
// IsInterleave: can s3 be formed by weaving s1 and s2 without reordering either? // dp[i][j] = the first i letters of s1 and j letters of s2 can form the first i+j letters of s3. func IsInterleave(s1, s2, s3 string) bool { if len(s1)+len(s2) != len(s3) { return false } dp := make([][]bool, len(s1)+1) for i := range dp { dp[i] = make([]bool, len(s2)+1) } dp[0][0] = true for i := 0; i <= len(s1); i++ { for j := 0; j <= len(s2); j++ { if i > 0 && dp[i-1][j] && s1[i-1] == s3[i+j-1] { dp[i][j] = true } if j > 0 && dp[i][j-1] && s2[j-1] == s3[i+j-1] { dp[i][j] = true } } } return dp[len(s1)][len(s2)] } - 7.Longest Increasing Path in a MatrixHard
Because the path must strictly increase, there are no cycles. Which results can you cache?
DFS with memoization: longest(r,c) = 1 + max over neighbours with larger values; cache per cell.
Target: O(m·n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func longestIncreasingPath(matrix [][]int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the 2-D Dynamic Programming lesson page.
// LongestIncreasingPath: memoized DFS. Strictly increasing steps cannot form a cycle, // so every cell's answer can be cached the first time it is computed. func LongestIncreasingPath(m [][]int) int { if len(m) == 0 { return 0 } memo := make([][]int, len(m)) for i := range memo { memo[i] = make([]int, len(m[0])) } var dfs func(r, c int) int dfs = func(r, c int) int { if memo[r][c] != 0 { return memo[r][c] } best := 1 for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} { nr, nc := r+d[0], c+d[1] if nr >= 0 && nr < len(m) && nc >= 0 && nc < len(m[0]) && m[nr][nc] > m[r][c] { best = max(best, 1+dfs(nr, nc)) } } memo[r][c] = best return best } longest := 0 for r := range m { for c := range m[r] { longest = max(longest, dfs(r, c)) } } return longest } - 8.Distinct SubsequencesHard
When the characters match you may use the match or skip the character in s.
dp[i][j] = dp[i−1][j] (skip s[i−1]) + (s[i−1]==t[j−1] ? dp[i−1][j−1] : 0); dp[i][0] = 1.
Target: O(m·n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func numDistinct(s string, t string) intTested with go test. Try it yourself first, then compare. It is explained step by step on the 2-D Dynamic Programming lesson page.
// NumDistinct: how many ways does t appear as a subsequence of s? // dp[j] = ways to build the first j letters of t from the part of s seen so far. func NumDistinct(s, t string) int { dp := make([]int, len(t)+1) dp[0] = 1 for i := 0; i < len(s); i++ { for j := len(t); j >= 1; j-- { // descending so dp[j-1] still holds the previous row if s[i] == t[j-1] { dp[j] += dp[j-1] } } } return dp[len(t)] } - 9.Edit DistanceMedium
Insert, delete and replace each correspond to moving in a different direction in the table.
dp[i][j] = dp[i−1][j−1] if the characters match, else 1 + min(insert dp[i][j−1], delete dp[i−1][j], replace dp[i−1][j−1]).
Target: O(m·n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func minDistance(word1 string, word2 string) intTested with go test. Try it yourself first, then compare. It is explained step by step on the 2-D Dynamic Programming lesson page.
// MinDistance: fewest insert / delete / replace edits to turn a into b. // State: dp[i][j] = edits to turn a[:i] into b[:j]. func MinDistance(a, b string) int { dp := make([][]int, len(a)+1) for i := range dp { dp[i] = make([]int, len(b)+1) dp[i][0] = i // delete everything } for j := 0; j <= len(b); j++ { dp[0][j] = j // insert everything } for i := 1; i <= len(a); i++ { for j := 1; j <= len(b); j++ { if a[i-1] == b[j-1] { dp[i][j] = dp[i-1][j-1] } else { dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) // replace, delete, insert } } } return dp[len(a)][len(b)] } - 10.Burst BalloonsHard
Think about which balloon you burst LAST in a range — then its neighbours are fixed.
Interval DP on the padded array: dp[l][r] = max over k of dp[l][k] + dp[k][r] + nums[l]·nums[k]·nums[r].
Target: O(n³) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func maxCoins(nums []int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the 2-D Dynamic Programming lesson page.
// MaxCoins: interval DP. Choose the balloon k that bursts LAST in (l, r); // then its neighbours are the fixed ends l and r, and the two sides are independent subproblems. func MaxCoins(nums []int) int { a := append([]int{1}, append(append([]int{}, nums...), 1)...) n := len(a) dp := make([][]int, n) for i := range dp { dp[i] = make([]int, n) } for length := 2; length < n; length++ { for l := 0; l+length < n; l++ { r := l + length for k := l + 1; k < r; k++ { dp[l][r] = max(dp[l][r], dp[l][k]+dp[k][r]+a[l]*a[k]*a[r]) } } } return dp[0][n-1] } - 11.Regular Expression MatchingHard
A "*" applies to the character before it: zero copies, or one more copy.
dp[i][j] over prefixes. If p[j−1] is "*": zero copies dp[i][j−2], or (s[i−1] matches p[j−2]) and dp[i−1][j]. Otherwise characters (or ".") must match and dp[i−1][j−1] must hold.
Target: O(m·n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func isMatch(s string, p string) boolTested with go test. Try it yourself first, then compare. It is explained step by step on the 2-D Dynamic Programming lesson page.
// IsMatch: regular expression matching with '.' and '*'. // dp[i][j] = the first i characters of s match the first j characters of p. func IsMatch(s, p string) bool { dp := make([][]bool, len(s)+1) for i := range dp { dp[i] = make([]bool, len(p)+1) } dp[0][0] = true for j := 2; j <= len(p); j++ { if p[j-1] == '*' { dp[0][j] = dp[0][j-2] // "a*" can match the empty string } } for i := 1; i <= len(s); i++ { for j := 1; j <= len(p); j++ { if p[j-1] == '*' { dp[i][j] = dp[i][j-2] // zero copies of the starred letter if p[j-2] == '.' || p[j-2] == s[i-1] { dp[i][j] = dp[i][j] || dp[i-1][j] // one more copy } } else if p[j-1] == '.' || p[j-1] == s[i-1] { dp[i][j] = dp[i-1][j-1] } } } return dp[len(s)][len(p)] }