LeetCode LCR 098. 不同路径
题目描述
题意分析
机器人从
m × n网格的左上角走到右下角，每一步只能向右或向下一格，求不同路径的条数。只统计数量，不需要列出具体路径。不能回头意味着到达某个格子后，可选的后续走法只由位置决定，可以将到达同一位置的路径合并计数。
解法：滚动累加网格路径数
核心思路
[!blue]
到达
(i, j)的最后一步只能从上方(i - 1, j)或左方(i, j - 1)出发。两类路径的最后一步不同，互不重叠；每条合法路径又必然属于其中一类。因此设f[i][j]为到达该格子的路径数，就有f[i][j] = f[i - 1][j] + f[i][j - 1]。第一行只能一直向右，第一列只能一直向下，路径数都为 1。起点也记为 1，表示尚未移动的那条路径，而不是已经走过一步。
每一行只依赖上一行和本行左侧，可以用长度为
n的dp保存一行。初始化全部为 1，相当于已经求出第一行；之后逐行从左到右更新。写入dp[j]之前，它还是上方格子的旧值，而dp[j - 1]已是本行左侧的新值，所以执行dp[j] += dp[j - 1]正好合并两个来源。每行第 0 列保持为 1，处理完最后一行后，
dp[n - 1]就是终点计数。题目保证答案不超过 $2\times10^9$；任一中间格子的路径都能接上固定后缀到达终点，所以中间计数也不会大于最终答案。
解题步骤
- 创建长度为
n的数组，全部初始化为 1。- 从第二行开始逐行处理，每行从第 1 列向右更新。
- 将上方旧值与左侧新值相加，写回
dp[j]。- 返回最后一列的
dp[n - 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];
}
}
func uniquePaths(m int, n int) int {
dp := make([]int, n)
for j := 0; j < n; j++ {
dp[j] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
// dp[j] 是上方路径数，dp[j-1] 是左侧路径数。
dp[j] += dp[j-1]
}
}
return dp[n-1]
}
复杂度分析
- 时间复杂度：$O(mn)$，每个格子只做常数次操作。
- 空间复杂度：$O(n)$，只保存一行路径数。
关键点总结
[!green]
- 路径按最后一步分类，不同来源的数量相加。
- 滚动更新同时需要上方旧值和左侧新值，因此必须从左到右。
- 只有一行或一列时，相应循环自然跳过，答案仍为 1。
易错点总结
[!yellow]
- 全部初始化为 0 会丢失起点和首行的路径，后续无法产生有效计数。
- 第 0 列只有上方一个来源，不应执行读取
dp[j - 1]的通用转移。- 倒序更新会读到上一行的左侧值，不能代表从本行左侧到达的路径。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 63. 不同路径 II | 中等 | 在只能向右或向下的路径计数中增加障碍，需要把不可达格子的方案数清零。 |
| 64. 最小路径和 | 中等 | 可达方向相同，原题最小化路径代价，本题累加所有可行走法数量。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！