Grid DP

1. 1.Unique Paths
   Grid DP path counting: 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 min cost: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])medium
4. 4.Triangle
   Bottom-up accumulation: dp[r][c] += min(dp[r+1][c], dp[r+1][c+1])medium
5. 5.Minimum Falling Path Sum
   Grid DP: dp[r][c] = matrix[r][c] + min(upper-left, up, upper-right)medium
6. 6.Maximal Square
   Grid DP square growth: dp[r][c] = 1 + min(top, left, diagonal) for 1smedium
7. 7.Dungeon Game
   Reverse Grid DP: compute min health needed from destination (E) to start (S)hard
8. 8.Cherry Pickup
   3D/2D Grid DP with 2 simultaneous paths: dp[r1][c1][r2]hard
9. 9.Cherry Pickup II
   Two-agent Grid DP: dp[row][col1][col2] evaluating 9 next column pairshard
10. 10.Count Square Submatrices with All Ones
    Grid DP: dp[r][c] = min(top, left, diagonal) + 1; answer = sum(dp)medium
11. 11.Minimum Path Cost in a Grid
    Grid DP + edge transition costs between adjacent rowsmedium
12. 12.Out of Boundary Paths
    3D Grid DP: dp[r][c][moves] counting paths exiting grid boundsmedium
13. 13.Number of Paths With Maximum Score
    Grid DP tracking pairs: (maxScore, countWays)hard
14. 14.Paths in Matrix Whose Sum Is Divisible by K
    3D Grid DP state: dp[r][c][rem] where rem = pathSum % Kmedium
15. 15.Maximum Non-Negative Product in a Matrix
    Grid DP tracking maxProduct and minProduct due to negative sign flipsmedium
16. 16.Minimum Number of Visited Cells in a Grid — advanced
    Grid DP + monotonic stack or segment tree range minimumshard
17. 17.Longest Increasing Path in a Matrix — DFS + Memoization
    DFS + Memoization for 4-directional strictly increasing grid pathshard
18. 18.Unique Paths III — compare with Backtracking
    Grid Backtracking / Bitmask DP visiting all empty cells exactly oncehard

1. 19.Falling Path Variants
   Multi-direction upper neighbor grid path transitionsmedium
2. 20.Grid DP with Obstacles
   Zeroing unreachable cell path counts behind obstaclesmedium
3. 21.Grid DP with Extra State
   3D DP state expansion dp[r][c][k] for remaining resource kmedium
4. 22.Two-Agent Grid DP
   Simultaneous 2-robot traversal state dp[row][c1][c2]hard
5. 23.Maximum Path Sum in Matrix
   Directional grid score maximization DPmedium
6. 24.Minimum Health / Resource DP
   Reverse destination-to-source health survival DPhard
7. 25.Grid DP Space Optimization
   Reducing O(R*C) grid DP table to 1D row array O(C)medium

1. Movement only from fixed directions?Grid DP
2. Need count paths?dp[r][c] = top + left
3. Need minimum cost?dp[r][c] = cell + min(top, left)
4. Need maximum score?dp[r][c] = cell + max(top, left)
5. Dependencies depend on future requirements?Reverse DP (End → Start)

package main

import "fmt"

// Minimum Path Sum 2D Matrix DP: O(R * C) time and space
func minPathSum(grid [][]int) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }
    r, c := len(grid), len(grid[0])
    dp := make([][]int, r)
    for i := range dp {
        dp[i] = make([]int, c)
    }

    // Base Case initialization
    dp[0][0] = grid[0][0]
    for j := 1; j < c; j++ { dp[0][j] = dp[0][j-1] + grid[0][j] }
    for i := 1; i < r; i++ { dp[i][0] = dp[i-1][0] + grid[i][0] }

    // Fill Matrix
    for i := 1; i < r; i++ {
        for j := 1; j < c; j++ {
            minPrev := dp[i-1][j] // top
            if dp[i][j-1] < minPrev {
                minPrev = dp[i][j-1] // left
            }
            dp[i][j] = grid[i][j] + minPrev
        }
    }
    return dp[r-1][c-1]
}

// Unique Paths Space-Optimized: O(C) space
func uniquePaths(m int, n int) int {
    dp := make([]int, n)
    for j := 0; j < n; j++ { dp[j] = 1 } // First row

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

func main() {
    grid := [][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}
    fmt.Println("Min Path Sum:", minPathSum(grid)) // Output: 7
    fmt.Println("Unique Paths:", uniquePaths(3, 7)) // Output: 28
}

Core Grid DP Patterns & Operations

Define dp[r][c] Cell Meaning → Allowed Movement → Combine Incoming Neighbors
Obstacle Cell → Set dp[r][c] = 0 to break path flow
Dungeon Game → Reverse DP (fill destination-to-start health requirements)
Falling Path → Final answer is min(last row), NOT always bottom-right cell
Space Compression → Keep 1D row array dp[c] to reduce O(R*C) to O(C)

Grid DP Variants & Algorithm Distinctions

Common Interview Mistakes

• • Assuming every grid matrix problem is Grid DP (could be BFS, DFS, Dijkstra, or Backtracking).
• • Failing to set blocked obstacle cells to 0, allowing paths to pass through walls.
• • Using 0 for minimum path cost initializations instead of infinity (INF).
• • Automatically returning dp[R-1][C-1] when the answer is min(last row) in Falling Path DP.
• • Filling the matrix in the wrong direction when dependencies require reverse end-to-start fill (e.g. Dungeon Game).
• • Forgetting extra state dimensions when path remainder or obstacle removals affect future choices.
• • Overwriting in-place grid cells prematurely during space optimization when original costs are still needed.
• • Failing to handle matrix boundary guards (r-1 < 0 or c-1 < 0), causing index out-of-bounds panics.
• • Allocating a massive R x C matrix without checking memory constraints (Memory Limit Exceeded).

Interview Rules

Fixed directional movement + grid? → Grid DP
Rule 1                              → Define dp[r][c] cell meaning explicitly
Rule 2                              → Set base starting cells & obstacle zeroes
Rule 3                              → Identify allowed incoming movements (top, left, diagonal)
Rule 4                              → Combine: + for paths, min for costs, max for scores
Rule 5                              → Reverse requirements (Dungeon Game) = Fill End to Start
Rule 6                              → Compress space to 1D row array O(C)
Time Complexity                     → Cells × Transitions (O(R * C) or O(R * C * K))
Space Complexity                    → O(R * C) Matrix or O(C) Compressed Row

💡 Golden Rule: For every cell, define exactly what answer it stores, then combine the already-solved cells that are allowed to lead into it.

Grid DP State: dp[r][c]
Goal Operations: Path count (+), Min cost (min), Max score (max), Square size (min+1)
Obstacles: Set dp[r][c] = 0
Dungeon Game: Reverse fill (Destination → Start)
Falling Path DP: Return min(last row)
Space Optimization: Reduce O(R*C) matrix to O(C) row array