Dynamic Programming • Pattern

DP on 2D Grids

Explore how to solve grid traversal problems using dynamic programming by analyzing state transitions from adjacent cells.

Try Interactive Simulator

Overview

Grid DP is extremely common. The state `dp[r][c]` typically represents the cost, max profit, or number of ways to reach cell `(r, c)`.

Directional Constraints

Since we usually can only move Right or Down, we can guarantee that when calculating `dp[r][c]`, both `dp[r-1][c]` and `dp[r][c-1]` are already computed.

Base Cases

The starting cell `(0, 0)` is initialized based on the problem (e.g. `1` for path counting, `grid[0][0]` for path sum). Boundaries need bounds checking.

Space Optimization

Because `dp[r][c]` only depends on the current row and the previous row, we can often optimize the O(R * C) space down to O(C) by keeping a 1D array.

0

Code Tracker

:::

1let dp = Array(R).fill().map(() => Array(C).fill(0));

2dp[0][0] = 1;

3for (let r = 0; r < R; r++) {

4 for (let c = 0; c < C; c++) {

5 if (r === 0 && c === 0) continue;

6 let top = r > 0 ? dp[r-1][c] : 0;

7 let left = c > 0 ? dp[r][c-1] : 0;

8 dp[r][c] = top + left;

9 }

10}

Dp On 2d Grids

Dp On 2d Grids

DP on 2D Grids

Overview

Directional Constraints

Base Cases

Space Optimization

DP on 2D Grids

Overview

Directional Constraints

Base Cases

Space Optimization