62. 不同路径
题目描述
有一个 m 行 n 列的网格。机器人从左上角的格子出发，要走到右下角的格子。
每一步只能向右或向下移动一格。
返回从起点走到终点的不同路线总数。
示例 1
输入：m = 3, n = 7 输出：28
示例 2
输入：m = 3, n = 2 输出：3
解释：共 3 条路线：右下下、下下右、下右下。
数据范围
1 <= m, n <= 100- 保证答案不超过
2 * 10^9。
解题思路：动态规划（一维滚动）
网格状态为上方和左方路径数之和，使用一维数组滚动每一行。
为什么正确
dp[j] 在更新前是上方格子的路径数，更新后是当前行该格的路径数。
复杂度分析
时间 O(mn)，空间 O(n)。
易错点
一维压缩时必须从左到右更新，因为 dp[j-1] 需要是当前行的新值。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[-1]class Solution {
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];
}
}class Solution {
public:
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];
}
};func uniquePaths(m int, n int) int {
dp := make([]int, n)
for j := range dp {
dp[j] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[j] += dp[j-1]
}
}
return dp[n-1]
}var uniquePaths = function(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];
};function uniquePaths(m: number, n: number): number {
const dp: number[] = 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];
};其他解法
动态规划通用、可扩展到带障碍物的情况；组合数学直接给出公式，O(min(m,n)) 时间、O(1) 空间，但只适用于无障碍的网格。
解法 2：组合数学 时间 O(min(m,n))，空间 O(1)
从左上角走到右下角，一共要走 m+n-2 步，其中恰好 m-1 步向下、n-1 步向右。不同路径数就是从 m+n-2 步里选出 m-1 步向下的方案数 C(m+n-2, m-1)。累乘时依次乘以 n, n+1, … 再除以 1, 2, …，每一步的中间结果都是组合数，一定能整除。
时间和空间都更优，但需要看出计数本质是组合数。累乘过程中要注意溢出，C++/Java 需要用 64 位整数。遇到障碍物（第 63 题）时这种方法就不适用了。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 从 m+n-2 步中选出 m-1 步向下
ans = 1
x = n
for y in range(1, m):
ans = ans * x // y
x += 1
return ansclass Solution {
public int uniquePaths(int m, int n) {
long ans = 1;
for (long x = n, y = 1; y < m; x++, y++) {
ans = ans * x / y;
}
return (int) ans;
}
}class Solution {
public:
int uniquePaths(int m, int n) {
long long ans = 1;
for (long long x = n, y = 1; y < m; x++, y++) {
ans = ans * x / y;
}
return (int)ans;
}
};func uniquePaths(m int, n int) int {
ans := 1
for x, y := n, 1; y < m; x, y = x+1, y+1 {
ans = ans * x / y
}
return ans
}var uniquePaths = function(m, n) {
let ans = 1;
for (let x = n, y = 1; y < m; x++, y++) {
ans = Math.floor(ans * x / y);
}
return ans;
};function uniquePaths(m: number, n: number): number {
let ans = 1;
for (let x = n, y = 1; y < m; x++, y++) {
ans = Math.floor(ans * x / y);
}
return ans;
}