Dynamic Programming • 2D Grids

Grid Unique Paths

Find the number of possible unique paths from the top-left to the bottom-right of a grid, moving only down or right.

Overview

This is the "Hello World" of 2D Grid DP. You are placed at `(0, 0)` and must reach `(m-1, n-1)` moving only down and right.

The State

Let `dp[r][c]` be the number of unique paths to reach the cell at row `r` and column `c`.

The Base Cases

Any cell in the first row can only be reached by moving right. Any cell in the first column can only be reached by moving down. Thus, they all have exactly 1 path.

The Transition

For any inner cell, you could have arrived from the cell directly above it, or the cell directly to its left. Thus, `dp[r][c] = dp[r-1][c] + dp[r][c-1]`.

Code Tracker

:::

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

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

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

4 if (r === 0 || c === 0) {

5 dp[r][c] = 1;

6 } else {

7 dp[r][c] = dp[r-1][c] + dp[r][c-1];

8 }

9 }

10}