Unique Paths
A robot starts at the top-left corner of an m × n grid and can move only right or down. Count the number of distinct paths to the bottom-right corner.
- 1 ≤ m, n ≤ 100
- The answer fits in a 32-bit integer
- Count paths on a grid with restricted moves
- A cell is entered from above or from the left
- Grid DP with a single row of state
Counting or optimizing over choices where a brute-force recursion revisits the same state signals DP: define the state so the answer to a state depends only on smaller states, then memoize or fill a table bottom-up. Subsequence (not subarray) wording, "number of ways", and "minimum/maximum over all choices" are the classic tells.
Let paths[r][c] be the number of ways to reach cell (r, c). Cells in the first row or column have exactly one path; every other cell satisfies paths[r][c] = paths[r-1][c] + paths[r][c-1]. Fill row by row keeping only the current row, so paths[c] += paths[c - 1]. The last entry is the answer.
- Every path is a sequence of m−1 downs and n−1 rights, so the answer is the binomial coefficient C(m+n−2, m−1), computable in O(m + n). With obstacles the DP is required.