Unique Paths
Medium· grid DP
Problem
A robot starts in the top-left cell of an m × n grid and can only move right or down. Count the distinct paths it can take to reach the bottom-right cell.
Examples
Input: m = 3, n = 7
Output: 28
Input: m = 3, n = 2
Output: 3
Right-Down-Down, Down-Right-Down, Down-Down-Right.
Constraints
- • 1 <= m, n <= 100
- • The answer fits in a 32-bit signed integer
Hints & approach
Hint 1
You can enter any cell only from above or from the left.
Hint 2
Cells in the first row or first column have exactly one path.
Hint 3
paths[i][j] = paths[i-1][j] + paths[i][j-1]; a single row array is enough.
Approachtry the hints first
Let paths[i][j] be the number of ways to reach cell (i, j). The first row and column are all 1. Every other cell sums the cell above and the cell to the left. Keep one row of length n and update it left to right, so row[j] += row[j-1]. Alternatively, the answer is the binomial coefficient C(m+n-2, m-1).
Time O(m·n) · Space O(n)