Dynamic programming: unique paths

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

The key DP insight: to land on any cell, the robot arrived either from the left or from above. So the number of ways to reach a cell is the sum of the ways to reach its left neighbor and its top neighbor:

ways[r][c] = ways[r-1][c] + ways[r][c-1]

Every cell in the top row and left column has exactly one way to reach it (keep going straight), which seeds the table. You can collapse the 2-D table into a single row that you update left-to-right.

row = [1] * n          # top row: one path to each cell
# for each lower row, row[c] += row[c-1]

Your task

Write unique_paths(m, n) returning the number of distinct right/down paths from the top-left to the bottom-right of an m-row by n-column grid.

unique_paths(3, 7)   # 28
unique_paths(3, 2)   # 3
unique_paths(1, 1)   # 1   (already there)
unique_paths(3, 3)   # 6

Hint: build a row of n ones and, for each of the remaining m - 1 rows, add each cell's left neighbor into it. The last value is your answer.