Notes
All notes

Unique Paths: filling a 2D DP table

Problem. A robot sits in the top-left corner of an m × n grid. It can only move down or right, and it wants to reach the bottom-right corner. How many distinct paths are there?

m = 3, n = 4  →  10 paths

Take the grid below. S is the start, E is the end, and the thick line is one valid path — three rights and two downs, in the order right, down, right, down, right.

\begin{tikzpicture}[font=\small]
  \foreach \i/\j in {0/0,0/1,1/1,1/2,2/2,2/3} {
    \fill[orange!25] (\j,2-\i) rectangle ++(1,1);
  }
  \draw[step=1,thick,black!45] (0,0) grid (4,3);
  \node[font=\large\bfseries] at (0.5,2.5) {S};
  \node[font=\large\bfseries] at (3.5,0.5) {E};
  \draw[->,very thick,orange] (0.85,2.5) -- (1.5,2.5);
  \draw[->,very thick,orange] (1.5,2.5) -- (1.5,1.5);
  \draw[->,very thick,orange] (1.5,1.5) -- (2.5,1.5);
  \draw[->,very thick,orange] (2.5,1.5) -- (2.5,0.5);
  \draw[->,very thick,orange] (2.5,0.5) -- (3.15,0.5);
\end{tikzpicture}

Why brute force explodes

You could enumerate every sequence of moves: a path is some interleaving of m-1 downs and n-1 rights, so there are \(\binom{m+n-2}{m-1}\) of them. For a 3 × 4 grid that is only \(\binom{5}{2} = 10\), but for a 20 × 20 grid it is \(\binom{38}{19} \approx 3.5 \times 10^{10}\) — far too many to walk one by one.

The trick is that we do not need to enumerate paths at all. We only need to count them, and counting has structure: the number of paths to a cell depends only on the two cells you could have arrived from.

The idea: every cell is a sum of its neighbours

Let dp[i][j] be the number of distinct paths from S to the cell in row i and column j (0-indexed, top-left is (0, 0)).

Think about the last move into (i, j). The robot came either:

There is no third option. Every path ending at (i-1, j) becomes exactly one path ending at (i, j) by appending a down move, and likewise on the left. The two sets of paths are disjoint (their final moves differ) and together cover every path. So the counts simply add:

\[ dp[i][j] = dp[i-1][j] + dp[i][j-1] \]

Base cases

The first row and the first column each have exactly one path: along the top edge you can only go right, and down the left edge you can only go down. So

\[ dp[0][j] = 1 \quad \text{and} \quad dp[i][0] = 1 \]

The answer we want is the bottom-right cell, dp[m-1][n-1].

Why the table fills in order

The recurrence reads (i-1, j) and (i, j-1) — a cell above and a cell to the left. So a cell is ready as soon as those two are ready. Filling row by row, left to right respects that exactly: by the time we reach (i, j), the whole row above is done and the cell to its left in the current row is done.

Dry run on 3 × 4

Step 1 — base cases. Write 1 across the top row and down the left column. Everything else is still unknown. These are the only cells that are given rather than computed.

\begin{tikzpicture}[font=\large]
  \foreach \j in {0,1,2,3} { \fill[green!22] (\j,2) rectangle ++(1,1); }
  \foreach \i in {0,1,2} { \fill[green!22] (0,2-\i) rectangle ++(1,1); }
  \draw[step=1,thick,black!50] (0,0) grid (4,3);
  \foreach \j in {0,1,2,3} { \node at (\j+0.5,2.5) {1}; }
  \foreach \i in {1,2} { \node at (0.5,2.5-\i) {1}; }
\end{tikzpicture}

Step 2 — the first row of the interior. Now every cell can be computed from its top neighbour and its left neighbour. Look at (1, 1): from above comes dp[0][1] = 1 and from the left comes dp[1][0] = 1, so dp[1][1] = 1 + 1 = 2. The two blue arrows are exactly those two terms.

\begin{tikzpicture}[font=\large]
  \foreach \j in {0,1,2,3} { \fill[green!22] (\j,2) rectangle ++(1,1); }
  \foreach \i in {0,1,2} { \fill[green!22] (0,2-\i) rectangle ++(1,1); }
  \foreach \j in {1,2,3} { \fill[orange!22] (\j,1) rectangle ++(1,1); }
  \draw[step=1,thick,black!50] (0,0) grid (4,3);
  \foreach \j in {0,1,2,3} { \node at (\j+0.5,2.5) {1}; }
  \node at (0.5,1.5) {1};
  \node at (1.5,1.5) {2};
  \node at (2.5,1.5) {3};
  \node at (3.5,1.5) {4};
  \draw[->,thick,blue] (1.5,2.32) -- (1.5,1.68);
  \draw[->,thick,blue] (0.68,1.5) -- (1.32,1.5);
\end{tikzpicture}

Continuing across the row: dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3 and dp[1][3] = dp[0][3] + dp[1][2] = 1 + 3 = 4.

Step 3 — the last row. The same rule, one row lower. For the corner: dp[2][3] = dp[1][3] + dp[2][2] = 4 + 6 = 10. The cell above is blue, the cell to the left is green, and their sum is the answer.

\begin{tikzpicture}[font=\large]
  \fill[blue!25] (3,1) rectangle ++(1,1);
  \fill[green!30] (2,0) rectangle ++(1,1);
  \fill[orange!45] (3,0) rectangle ++(1,1);
  \draw[step=1,thick,black!50] (0,0) grid (4,3);
  \foreach \j in {0,1,2,3} { \node at (\j+0.5,2.5) {1}; }
  \node at (0.5,1.5) {1}; \node at (1.5,1.5) {2}; \node at (2.5,1.5) {3}; \node at (3.5,1.5) {4};
  \node at (0.5,0.5) {1}; \node at (1.5,0.5) {3}; \node at (2.5,0.5) {6}; \node at (3.5,0.5) {10};
\end{tikzpicture}

The finished table reads:

1   1   1   1
1   2   3   4
1   3   6  10   ← answer

Why the counts really add up

It is easy to nod along to the recurrence without believing it. A tiny example makes it concrete. In a 2 × 3 grid there are three paths: right-right-down, right-down-right, and down-right-right. Every path to the bottom-right cell ends with a move that came from the cell above it or the cell to its left — and those two groups of paths never overlap.

\begin{tikzpicture}[font=\small]
  \draw[step=1,thick,black!45] (0,0) grid (3,2);
  \draw[step=1,thick,black!45] (4,0) grid (7,2);
  \draw[step=1,thick,black!45] (8,0) grid (11,2);
  % RRD
  \draw[->,very thick,blue] (0.5,1.5) -- (1.5,1.5);
  \draw[->,very thick,blue] (1.5,1.5) -- (2.5,1.5);
  \draw[->,very thick,blue] (2.5,1.5) -- (2.5,0.5);
  % RDR
  \draw[->,very thick,green!55!black] (4.5,1.5) -- (5.5,1.5);
  \draw[->,very thick,green!55!black] (5.5,1.5) -- (5.5,0.5);
  \draw[->,very thick,green!55!black] (5.5,0.5) -- (6.5,0.5);
  % DRR
  \draw[->,very thick,orange] (8.5,1.5) -- (8.5,0.5);
  \draw[->,very thick,orange] (8.5,0.5) -- (9.5,0.5);
  \draw[->,very thick,orange] (9.5,0.5) -- (10.5,0.5);
  \node at (1.5,-0.4) {R R D};
  \node at (5.5,-0.4) {R D R};
  \node at (9.5,-0.4) {D R R};
\end{tikzpicture}

Three paths, and dp[1][2] = 3. The table is not storing paths — it is storing how many ways there are to get to each cell, which is all we ever need.

The code

def unique_paths(m, n):
    # dp[i][j] = number of paths to cell (i, j)
    dp = [[1] * n for _ in range(m)]      # base cases baked in
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

In Go:

func uniquePaths(m, n int) int {
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
		for j := range dp[i] {
			dp[i][j] = 1 // first row and first column
		}
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-1]
}

Space optimization

Look closely at the recurrence: dp[i][j] needs the cell above (previous row, same column) and the cell left (current row, previous column). The entire rest of the table is irrelevant. So keep a single array of length n representing the previous row, and update it left to right in place:

def unique_paths(m, n):
    dp = [1] * n                 # row 0
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]   # old dp[j] is the cell above,
                                 # dp[j-1] is already the cell to the left
    return dp[n - 1]

Before the update, dp[j] still holds the value from the row above; after the update it holds the current cell. Because we walk j left to right, dp[j-1] has already been refreshed to the current row. One array, same answer.

Complexity

Version Time Extra space
2D table \(O(m \cdot n)\) \(O(m \cdot n)\)
Rolling 1D array \(O(m \cdot n)\) \(O(n)\)

Every cell is visited once. The 1D version is a straightforward win when one dimension is small.

Edge cases