LeetCode 62. 不同路径
题目描述
✅ 62. 不同路径
题意分析
在
m行n列、没有障碍的网格中，从左上角走到右下角，每次只能向右或向下移动一格，求不同走法的总数。两条路径只要移动顺序不同，就视为不同路径；本题统计数量，不需要列出路径。任意合法路径都恰好向下走
m - 1步、向右走n - 1步。只有一行或一列时只有一种走法；起点和终点重合时，不移动也算一种走法。题目保证最终答案不超过2 × 10^9，可以用整数返回。
解法：一维动态规划
核心思路
[!blue]
先看二维状态：令
ways[i][j]表示从起点到第i行、第j列的路径数。到达一个内部格子的最后一步，只能来自上方或左方。每条到达上方的路径向下走一步，每条到达左方的路径向右走一步，都会得到到达当前格子的路径；两类路径最后一步不同，互不重复且覆盖全部可能，因此ways[i][j] = ways[i - 1][j] + ways[i][j - 1]。第一行只能一直向右，第一列只能一直向下，路径数都为
1。每个内部状态只依赖上一行同列和本行左邻居，所以没有必要保存整个网格，可以压缩成一行dp。首行生成后，每轮从左向右更新：赋值前的
dp[j]还表示上方格子的路径数，而dp[j - 1]已经更新成当前行左边格子的路径数。因此执行dp[j] += dp[j - 1]，正好实现二维转移。旧的上方状态使用后不再需要，可以原地覆盖。代码采用统一初始化：数组初始全零，只令
dp[0] = 1，然后从第0行开始扫描。第一次从左向右累加时，上方视为没有贡献，唯一的一条起点路径会依次传递到整行，使首行全部变成1。之后每轮正常叠加上方与左方；第一列不参与更新，始终保留唯一的向下路径。
解题步骤
- 创建长度为
n的整数数组dp，令dp[0] = 1，其余位置保持0。- 外层循环共处理
m行，包含第0行的生成过程。- 每行从第
1列开始向右更新dp[j] += dp[j - 1]，第一列保持为1。- 一行更新结束后，
dp表示这一行各格子的路径数；处理完最后一行，返回dp[n - 1]。
代码实现
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
// 第一列始终只有一种走法，首轮扫描由它逐列生成第一行。
dp[0] = 1;
for (int i = 0; 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)
// 第一列始终只有一种走法，首轮扫描由它逐列生成第一行。
dp[0] = 1
for i := 0; i < m; i++ {
for j := 1; j < n; j++ {
// 当前位置旧值来自上方，左边已更新为本行状态。
dp[j] += dp[j-1]
}
}
return dp[n-1]
}
复杂度分析
- 时间复杂度：$O(mn)$，逐行处理网格，每个内部格子做一次加法。
- 空间复杂度：$O(n)$，只保存一行的路径数。
关键点总结
[!green]
- 按最后一步把路径分成两类，才能说明为什么相加不会重复或漏计。
- 一维数组在更新途中同时保存上一行旧状态和当前行新状态，必须从左向右扫描。
- 只初始化
dp[0]时要从第0行开始；若先把整行设为1，则应从第1行开始。- 第一列保持为
1，单行、单列和单格网格都自然符合这套初始化。
解法：组合计数
核心思路
[!blue]
从起点到终点，总共必须走
steps = m + n - 2步，其中m - 1步向下，其余向右。只要决定哪些位置放向下的移动，整条路径就唯一确定；反过来，每条路径也唯一对应这组位置，因此答案是组合数C(m + n - 2, m - 1)。选择向下的位置与选择向右的位置一一对应，可以取
k = min(m - 1, n - 1)，计算C(steps, k)，减少乘除次数。起点终点重合或只有一行一列时，k = 0，不需要选择任何位置，答案自然为1。不直接计算阶乘，而是从
ways = 1开始，让i从1增加到k，每次执行ways = ways * (steps - k + i) / i。第i次得到的正好是C(steps - k + i, i)，所以先乘后除的结果始终为整数；若提前做除法，截断小数可能破坏结果。虽然题目保证最终答案能用 32 位整数表示，乘法后、除法前的临时值仍可能更大。因此 Java 用
long、Go 用int64计算，最后再转成返回类型。按题目的网格大小和答案上界，64 位整数足以容纳这些中间乘积。
解题步骤
- 计算总步数
steps = m + n - 2，选择数k = min(m - 1, n - 1)。- 将 64 位整数
ways初始化为1。- 对
i = 1到k，先乘上steps - k + i，再除以i，逐步得到目标组合数。- 返回
ways转成整数后的结果。
代码实现
class Solution {
public int uniquePaths(int m, int n) {
int steps = m + n - 2;
int k = Math.min(m - 1, n - 1);
long ways = 1;
for (int i = 1; i <= k; i++) {
ways = ways * (steps - k + i) / i;
}
return (int) ways;
}
}
func uniquePaths(m int, n int) int {
steps := m + n - 2
k := m - 1
if n-1 < k {
k = n - 1
}
ways := int64(1)
for i := 1; i <= k; i++ {
ways = ways * int64(steps-k+i) / int64(i)
}
return int(ways)
}
复杂度分析
- 时间复杂度：$O(min(m, n))$，计算较少一种移动方向所需的位置选择。
- 空间复杂度：$O(1)$，只保存固定数量的整数变量。
关键点总结
[!green]
- 固定向下与向右的次数后，路径计数等价于在移动序列中选位置。
- 组合数的对称性允许选择较少的方向来计算。
- 逐项先乘后除，避免阶乘过大和整数提前截断；中间结果使用 64 位整数。
- 该公式依赖没有障碍的完整网格，加入障碍后需重新处理可达性，不能直接套用。
易错点总结
[!yellow]
dp全部保持为零，没有起点路径作为初始贡献，后续累加仍然全是零。- 一维 DP 从右向左更新，会读到上一行的左邻居，而不是本行左边格子的路径数。
- 内层从
j = 0开始，会访问不存在的dp[-1]；第一列本来就不需要转移。- 已将整行初始化为
1，却仍按本文循环处理m行，相当于多计算了一行。- 组合计数直接计算阶乘，或先做整数除法，都可能得到错误结果；应逐项先乘后除，并用 64 位整数保存中间值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 63. 不同路径 II | 中等 | 在只能向右或向下的路径计数中增加障碍，需要把不可达格子的方案数清零。 |
| 64. 最小路径和 | 中等 | 可达方向相同，原题最小化路径代价，本题累加所有可行走法数量。 |
| 120. 三角形最小路径和 | 中等 | 在网格上从前驱状态递推路径；本题累加向右向下的路径数，该题按三角形相邻位置求最小路径。 |
| 931. 下降路径最小和 | 中等 | 在网格上从前驱状态递推路径；本题累加向右向下的路径数，该题允许来自上一行三个相邻列。 |
| 980. 不同路径 III | 困难 | 不同路径系列。III 允许四方向移动，并要求每个空格恰好经过一次，需要在搜索中记录已访问格子。 |