62. Unique Paths
1. Description
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * $10^9$.
2. Example
Example 1
Input: m = 3, n = 7
Output: 28
Example 2
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
- Right -> Down -> Down
- Down -> Down -> Right
- Down -> Right -> Down
3. Constraints
- 1 <= m, n <= 100
4. Solutions
Dynamic Programming
Time complexity: O(mn)
Space complexity: O(n)
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> path_count(n, 1);
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
path_count[j] += path_count[j - 1];
}
}
return path_count.back();
}
};
Math && Combinations
Time complexity: O(m)
Space complexity: O(1)
// We must move right (n - 1) times and down (m - 1) times.
// The total number of paths equals the number of ways to arrange these moves:
// C(m + n - 2, m - 1) (or equivalently C(m + n - 2, n - 1)).
class Solution {
public:
int uniquePaths(int m, int n) {
int N = m + n - 2;
int k = min(m - 1, n - 1);
long long path_count = 1;
for (int i = 1; i <= k; ++i) {
// Since C(N, M) and C(N-1, M-1) are both integers,
// the multiplicative term must combine with C(N-1, M-1) to produce an exact integer result.
path_count = path_count * (N - k + i) / i;
}
return static_cast<int>(path_count);
}
};