2D Dynamic Programming

1. 1.Unique Paths
   2D Grid DP: dp[r][c] = dp[r-1][c] + dp[r][c-1]medium
2. 2.Unique Paths II
   Grid DP with obstacles: if obstacle dp[r][c] = 0, else top + leftmedium
3. 3.Minimum Path Sum
   Grid DP: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])medium
4. 4.Longest Common Subsequence
   2D String DP: match -> 1 + dp[i-1][j-1], else max(top, left)medium
5. 5.Edit Distance
   2D String DP: match -> dp[i-1][j-1], else 1 + min(insert, delete, replace)medium
6. 6.Longest Palindromic Subsequence
   2D Substring DP: match -> 2 + dp[i+1][j-1], else max(top, left)medium
7. 7.Distinct Subsequences
   2D String DP counting: match -> dp[i-1][j-1] + dp[i-1][j]hard
8. 8.Interleaving String
   2D String Boolean DP: dp[i][j] checks prefix match of s1 and s2 with s3medium
9. 9.0/1 Knapsack
   2D State dp[i][w]: max(skip dp[i-1][w], take val + dp[i-1][w-weight])medium
10. 10.Partition Equal Subset Sum — 2D version
    2D Boolean DP: dp[i][s] checks if subset sum s is possible using first i itemsmedium
11. 11.Target Sum — 2D thinking
    2D State dp[i][sum]: count ways using first i numbersmedium
12. 12.Triangle
    Grid DP accumulation: dp[r][c] += min(dp[r+1][c], dp[r+1][c+1])medium
13. 13.Minimum Falling Path Sum
    Grid DP: dp[r][c] = cell + min(left, center, right)medium
14. 14.Maximal Square
    2D Matrix: dp[r][c] = 1 + min(top, left, diagonal) for 1smedium
15. 15.Dungeon Game
    Reverse Grid DP: compute min health required from bottom-right to top-lefthard
16. 16.Longest Common Substring
    2D Matrix: match -> 1 + dp[i-1][j-1], else reset to 0medium
17. 17.Regular Expression Matching
    2D String Matching matrix handling . and * wildcardshard
18. 18.Wildcard Matching
    2D String Matching matrix handling ? and * wildcardshard
19. 19.Palindrome Partitioning DP
    2D Substring Palindrome table + 1D min cuts DPmedium
20. 20.Cherry Pickup
    3D/2D Grid DP with 2 simultaneous paths: dp[r1][c1][r2]hard

1. 21.Matrix Chain Multiplication
   Interval 2D DP: min cost to multiply matrix chain from i to jhard
2. 22.Burst Balloons
   Interval 2D DP: last balloon burst k in range (i, j)hard
3. 23.Stone Game variants
   Interval Game DP: max score difference dp[i][j]medium
4. 24.Boolean Parenthesization
   Interval DP: count true/false evaluations of boolean expressionhard
5. 25.Egg Dropping
   2D State dp[eggs][floors]: min moves in worst case scenariohard
6. 26.Longest Repeating Subsequence
   LCS 2D variant on same string with i != j constraintmedium
7. 27.Shortest Common Supersequence
   2D LCS table path reconstruction to build supersequencehard
8. 28.Count Palindromic Subsequences
   Interval 2D DP counting total palindromic subsequenceshard
9. 29.DP on Two Sequences
   2D Matrix alignment across two dynamic sequencesmedium
10. 30.Interval DP
    Generic diagonal fill DP by substring/subsegment lengthhard

1. Two things change in recursive state?dp[i][j]
2. Grid row + column?2D Grid DP
3. Two strings / sequences?2D String DP dp[i][j]
4. Item index + capacity?2D Knapsack DP
5. Substring / subsegment range (left, right)?Interval 2D DP

package main

import "fmt"

// Edit Distance 2D Matrix DP: O(M * N) time and space
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    // Base Case Rows and Columns (Empty String conversions)
    for i := 0; i <= m; i++ { dp[i][0] = i }
    for j := 0; j <= n; j++ { dp[0][j] = j }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                // min(Insert, Delete, Replace)
                ins := dp[i][j-1]
                del := dp[i-1][j]
                rep := dp[i-1][j-1]
                minOp := ins
                if del < minOp { minOp = del }
                if rep < minOp { minOp = rep }
                dp[i][j] = 1 + minOp
            }
        }
    }
    return dp[m][n]
}

// Space-Optimized 2D Grid DP (Unique Paths): O(Cols) space
func uniquePathsSpaceOptimized(m int, n int) int {
    dp := make([]int, n)
    for j := 0; j < n; j++ { dp[j] = 1 } // Row 0 base case

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[j] = dp[j] + dp[j-1] // top (dp[j]) + left (dp[j-1])
        }
    }
    return dp[n-1]
}

func main() {
    fmt.Println("Edit Distance:", minDistance("horse", "ros"))      // 3
    fmt.Println("Unique Paths:", uniquePathsSpaceOptimized(3, 7)) // 28
}

5 Major 2D DP Categories & Mechanics

Define dp[i][j] Cell Meaning → Base Row/Col → Transition → Target Cell
Grid DP → dp[r][c] depends on ↑ top, ← left
Two-String DP → dp[i][j] depends on ↖ diagonal, ↑ top, ← left
Interval DP → Filled by subsegment length (1 to N) along upper diagonals
Space Optimization → Compress 2D matrix O(M*N) to 1D row array O(N)

2D DP Fill Orders & Compression

Common Interview Mistakes

• • Coding 2D nested loops without explicitly defining what dp[i][j] represents.
• • Wrong base row or column initializations (e.g. failing to set Edit Distance base delete/insert costs).
• • Failing to use (N+1) x (M+1) dimensions for string matching DP, causing index bounds errors.
• • Confusing string character index s[i-1] with 1-based DP prefix index dp[i][j].
• • Filling Interval DP row-by-row instead of by increasing subsegment length.
• • Assuming the final answer is always bottom-right cell dp[N][M] (some problems require max across table).
• • Compressing 2D space to 1D prematurely before validating diagonal dependency requirements.
• • Confusing directional DP grids (top/left movement) with general 4-directional BFS graph shortest paths.
• • Allocating a massive 2D matrix without checking memory constraints (Memory Limit Exceeded).

Interview Rules

Two changing state variables → 2D DP
Rule 1                       → Define dp[i][j] cell meaning explicitly
Rule 2                       → Allocate (N+1) x (M+1) for string matching prefix bases
Rule 3                       → Determine dependency direction (↑ top, ← left, ↖ diagonal)
Rule 4                       → Interval DP = Fill diagonally by subsegment length 1 to N
Rule 5                       → Verify if target is dp[M][N] or max(dp matrix)
Rule 6                       → Compress 2D to 1D row array after table logic works
Time Complexity              → Cells × Work per Cell (O(N*M) or O(N³))
Space Complexity             → O(N*M) Matrix or O(M) Compressed Row

💡 Golden Rule: When two changing values are needed to completely describe the subproblem, make them the two DP dimensions and fill each cell only after the states it depends on are ready.

2D DP State: dp[i][j] (Grid, Two Strings, Knapsack, Intervals)
Golden Steps: Define Cell → Base Row/Col → Dependencies → Fill Order → Target
String DP: Use (N+1) x (M+1) table for empty string base cases
Dependencies: ↑ top, ← left, ↖ diagonal
Interval DP: Fill diagonally by subsegment length 1..N
Row Compression reduces O(N*M) memory to O(M)