A robot starts at the top-left corner of an m x n grid and wants to reach the bottom-right corner. It can only move right or down one cell at a time. Return the number of different paths it can take.
- 1 <= m, n <= 100
- The answer is at most 2 * 10^9
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force recursion explores both moves from every cell, about 2^(m+n) calls. State: dp[r][c] = number of paths from the start to cell (r, c). Recurrence: the last move came from above or from the left, so dp[r][c] = dp[r-1][c] + dp[r][c-1]. Base case: every cell in the first row or first column has exactly 1 path (a straight line). Memo makes the recursion O(m * n); the table fills row by row; and because row r only needs row r - 1, a single 1D array updated in place (row[c] += row[c-1]) works.
Algorithm
- Create
rowof lengthnfilled with 1 (the first row). - Repeat for each of the remaining
m - 1rows. - For
cfrom 1 ton - 1, setrow[c] += row[c - 1](above plus left). - Return
row[n - 1].
O(m * n)Space: O(n)m - 1 downs and n - 1 rights in some order, so the count is C(m + n - 2, m - 1). Compute it with a running product to avoid overflow, and mention both approaches in the interview.class Solution: def uniquePaths(self, m: int, n: int) -> int: row = [1] * n # first row for _ in range(1, m): for c in range(1, n): row[c] += row[c - 1] # above + left return row[n - 1]