Pattern Reference
Grid DP
"DP on 2D grids: unique paths, minimum path sum, dungeon game, cherry pickup, triangle, falling path sum."
Loading...
Deep Dive Tutorial
Grid DP is the simplest 2D DP. Every cell dp[i][j] summarizes the best answer for the subproblem ending at (i,j). Since movement is restricted (typically only right/down), the dependency graph is a DAG — we can fill it in topological order (row by row, left to right). The key is choosing what dp[i][j] represents.
| What dp[i][j] represents | Transition | Problem |
|---|---|---|
| Number of paths to (i,j) | dp[i-1][j] + dp[i][j-1] | Unique Paths |
| Min cost to reach (i,j) | grid[i][j] + min(dp[i-1][j], dp[i][j-1]) | Minimum Path Sum |
| Min health needed at (i,j) | max(1, min(right,down) - dungeon[i][j]) | Dungeon Game |
| Max gold collectible ending at (i,j) | grid[i][j] + max of valid predecessors | Maximum Gold |
| Max sum of submatrix corner at (i,j) | 2D prefix sum | Max Rectangle Sum |
Core Template
Grid DP — fill top-left to bottom-right
// dp[i][j] = best answer for subproblem "ending at cell (i,j)"
// Movement: only right (→) and down (↓)
const m = grid.length, n = grid[0].length;
const dp = Array.from({length:m}, () => new Array(n).fill(0));
// Base cases: top row (can only come from left)
dp[0][0] = f(grid[0][0]);
for (let j=1; j<n; j++) dp[0][j] = transition(dp[0][j-1], grid[0][j]);
// Left column (can only come from above)
for (let i=1; i<m; i++) dp[i][0] = transition(dp[i-1][0], grid[i][0]);
// Fill rest
for (let i=1; i<m; i++)
for (let j=1; j<n; j++)
dp[i][j] = combine(dp[i-1][j], dp[i][j-1], grid[i][j]);
return dp[m-1][n-1];
// Space optimization: only need previous row
// let prev = dp[0], curr;
// for (let i=1; ...) { curr = []; ... prev = curr; }Worked Problems
brain
Grid DP pattern guide:
- Moving right+down only → fill top-left to bottom-right
- Moving in all 4 directions → BFS/DFS with memoization
- "Min health at start" → fill backwards from goal
- "Count paths with obstacle" → dp[i][j]=0 if obstacle, else sum
- "Two agents moving simultaneously" → 3D dp[row][col1][col2]
- "Max square of 1s" → min(left, above, diagonal) + 1
Space optimization: if dp[i][j] only depends on row i-1, use two 1D arrays (prev and curr). If depends only on dp[i][j-1], use single 1D array in-place.
- Moving right+down only → fill top-left to bottom-right
- Moving in all 4 directions → BFS/DFS with memoization
- "Min health at start" → fill backwards from goal
- "Count paths with obstacle" → dp[i][j]=0 if obstacle, else sum
- "Two agents moving simultaneously" → 3D dp[row][col1][col2]
- "Max square of 1s" → min(left, above, diagonal) + 1
Space optimization: if dp[i][j] only depends on row i-1, use two 1D arrays (prev and curr). If depends only on dp[i][j-1], use single 1D array in-place.