Problem
A robot is at the top-left of an m×n grid. It can only move down or right. Count the number of unique paths to the bottom-right.
Example
Input: m = 3, n = 7
Output: 28Solution
DP: paths(i, j) = paths(i-1, j) + paths(i, j-1). First row and column have only 1 path each.
def unique_paths(m, n):
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1]
return dp[-1]function uniquePaths(m, n) {
const dp = new Array(n).fill(1);
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] += dp[j-1];
}
}
return dp[n-1];
}int uniquePaths(int m, int n) {
vector<int> dp(n, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j-1];
}
}
return dp[n-1];
}public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j-1];
}
}
return dp[n-1];
}Complexity
- Time: O(m * n)
- Space: O(n)
Explanation
We only need the previous row, so we can compress 2D dp to 1D. dp[j] += dp[j-1] computes dp[i][j] = dp[i-1][j] + dp[i][j-1] in place.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?