Dynamic Programming • 2D Grids

Unique Paths

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

Try Interactive Simulator

Overview

This is the "Hello World" of 2D grid DP. At any given cell, how did we get here? We must have come from either the cell directly above, or directly to the left.

The Recurrence

Since we can only arrive from UP or LEFT, the total number of unique paths to a cell is simply the sum of the paths to those two source cells: `dp[r][c] = dp[r-1][c] + dp[r][c-1]`.

Base Cases

Any cell in the very first row can only be reached by moving continuously Right. So `dp[0][c] = 1`. Similarly, the first column is all `1`s.

Math Alternative

This problem can also be solved in `O(min(M, N))` time using combinatorics: it's exactly `(M+N-2) Choose (M-1)`. But the DP approach is more extensible to obstacles.

Code Tracker

:::

1let dp = Array.from({ length: m }, () => new Array(n).fill(1));

2// We can init everything to 1 because the edges are 1,

3// and we just overwrite the inner cells.

4for (let r = 1; r < m; r++) {

5 for (let c = 1; c < n; c++) {

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

7 }

8}

9return dp[m - 1][n - 1];