LeetCode 62 · Medium · 2-D Dynamic Programming

Unique Paths

A robot starts in the top-left cell of an m × n grid and may only step right or down. Count the different routes it can take to the bottom-right cell.

O(m·n)time
O(n)space
right + downone row at a time

m and n: whole numbers from 1 to 8

+=

grid each cell = routes from it to the bottom-right · S start · F finish

public int uniquePaths(int m, int n) { int[] row = new int[n]; Arrays.fill(row, 1); // bottom row for (int i = 0; i < m - 1; i++) { int[] newRow = new int[n]; Arrays.fill(newRow, 1); // right column for (int j = n - 2; j >= 0; j--) { newRow[j] = newRow[j + 1] + row[j]; } row = newRow; } return row[0];}
i
—
j
—
row
—
newRow
—

Why it works

  1. Brute force walks every route: recurse right and down from the start. Every route is m+n−2 moves, so the tree has about 2m+n leaves.
  2. Routes add up. The first move from a cell is either right or down, and the two choices never share a route. So routes from a cell = routes from its right neighbour + routes from the cell below.
  3. One row is enough. A cell only reads the row below and the cell to its right, so the code keeps the row below (row) and builds the next one (newRow) right to left. O(m·n) time, O(n) space.
  4. Pitfall: the bottom row and the right column are all 1, not 0. From there the robot has exactly one route: straight along the edge.
  5. Closed form: a route is m−1 downs and n−1 rights in some order, so the answer is C(m+n−2, m−1). Follow-up, Unique Paths II (63): an obstacle cell holds 0 routes, and the same sum works around it.