Pattern Guide
Grid DP
"dp[i][j] depends on neighbors. Fill row by row."
Grid DP problems fill a 2D array where dp[i][j] depends on adjacent cells (above, left, or diagonal). Unique paths, minimum path sum, dungeon game, maximum gold, cherry pickup — all follow a left-to-right, top-to-bottom fill order with clean base cases at the edges.
18 min readdp problems →
Problems you can solve with this pattern
6 problems · click any to start solving
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; }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; }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.