Unique Paths

The problem

A grid has m rows and n columns. You start in the top-left cell and want to reach the bottom-right cell. Each move takes you one cell to the right or one cell down. Return the number of different paths. Two paths are different when they make their moves in a different order. In a grid with a single cell you are already there, and that counts as one path.

What to write

function solve(m: number, n: number): number

Input
m = 3
n = 7

Output
28

Input
m = 3
n = 2

Output
3

Constraints

Integer m and n from 1 to 15.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Every path makes the same moves in some order: m - 1 moves down and n - 1 moves right. Only the order differs. Following the paths one by one takes as many walks as there are paths, and a 15 by 15 grid already has 40116600 of them.

2. Hint 2: Ask a smaller question

   Take a grid with 2 rows and 3 columns and count its paths by hand. Now think about the last move of a path: which cells can that move come from? How many paths lead to each of those cells?

3. Hint 3: Name the pattern

   A path enters a cell from the cell above it or from the cell on its left, so the cell's number of paths is the sum of those two numbers. Working out an answer for every cell from answers already found, row by row, is two-dimensional dynamic programming. The signal: each cell depends only on earlier cells. Read the lesson on two-dimensional dynamic programming.

4. Hint 4: State the invariant

   Keep one row of counts. When a grid row is finished, each slot holds the number of paths from the top-left cell to that cell of the row. While you fill the next row, slots on your left already belong to the new row, and your own slot still holds the count from the row above.

5. Hint 5: Sketch the pseudocode

   row = a list of n ones. Repeat m - 1 times: for each position c from the second to the last, row[c] = row[c] + row[c - 1]. Return the last number in row.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Every cell receives paths from above and from the left. Initialize the first row to ones and update a single row of accumulated counts.

The slow way

From each cell, try the move right and the move down, and count 1 every time you arrive at the bottom-right cell. It is correct, but it walks every path separately. The 3 by 7 grid takes 119 cell visits for its 28 paths, and a 15 by 15 grid has 40116600 paths.

The insight

Many paths share their first moves, so walking each path separately repeats the same work. One number per cell is enough: how many paths reach it. A path's last move into a cell is down or right, so that number is the count for the cell above plus the count for the cell on the left. Reusing answers to smaller questions like this is called dynamic programming.

Step by step

1. Start with the top row: one path to each of its cells. A cell in the top row can only be reached by moving right all the way, so there is exactly one path to it. Only one row of counts is kept, and it starts as the top row.
2. Take each lower row in turn, from its second cell to its last. A row is built from the row above it, so the rows go top to bottom. The first cell of a row is reached only by moving straight down, so that cell keeps its 1 and is skipped.
3. Add the count on the left to the count kept from the row above. Before the update, the slot still holds the count for the cell above. The slot on its left is already finished for this row. Their sum is the count for this cell.
4. Return the last count: it belongs to the bottom-right cell. After the last pass the kept row is the bottom row of the grid, and its last slot is the bottom-right cell. With one row, or one column, no addition ever runs and the answer is the starting 1.

The same numbered steps are the comments in each solution.

function solve(m, n) {
  // 1. Start with the top row: one path to each of its cells
  const dp = Array(n).fill(1);
  // 2. Take each lower row in turn, from its second cell to its last
  for (let r = 1; r < m; r++)
    for (let c = 1; c < n; c++)
      // 3. Add the count on the left to the count kept from the row above
      dp[c] += dp[c - 1];
  // 4. Return the last count: it belongs to the bottom-right cell
  return dp[n - 1];
}

function solve(m: number, n: number): number {
  // 1. Start with the top row: one path to each of its cells
  const dp = Array(n).fill(1);
  // 2. Take each lower row in turn, from its second cell to its last
  for (let r = 1; r < m; r++)
    for (let c = 1; c < n; c++)
      // 3. Add the count on the left to the count kept from the row above
      dp[c] += dp[c - 1];
  // 4. Return the last count: it belongs to the bottom-right cell
  return dp[n - 1];
}

def solve(m, n):
    # 1. Start with the top row: one path to each of its cells
    dp = [1] * n
    # 2. Take each lower row in turn, from its second cell to its last
    for _ in range(1, m):
        for col in range(1, n):
            # 3. Add the count on the left to the count kept from the row above
            dp[col] += dp[col - 1]
    # 4. Return the last count: it belongs to the bottom-right cell
    return dp[-1]

Example 1, traced

Input
m = 3
n = 7

Output
28

Why it works

The top row and the first cell of every row are correct: one path each. Every other cell's paths split into two groups that share no path: those whose last move was down and those whose last move was to the right. If the counts above and on the left are correct, so is their sum, and both are always computed first.

Time and space

Time O(m × n), extra space O(n). Each of the m - 1 lower rows updates n - 1 slots with one addition each, so the time is O(m × n). A row needs only the row above it, so one row of n counts is kept and the space is O(n).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• The top row is already filled, so only m - 1 rows are left. Running the row loop m times computes one row too many: the 3 by 7 grid returns 84 instead of 28.
• Fill each row from left to right. Going right to left reads the left slot before that slot is updated, so it still belongs to the row above, and the 3 by 7 grid returns 4.
• Start the inner loop at the second cell. At the first cell, Python reads the last slot of the row and JavaScript reads undefined: the 3 by 7 grid gives 43 in Python and NaN in JavaScript.

Pattern

Two-dimensional dynamic programming. Builds on Climbing Stairs.

Keep going