LeetCode LCR 098. 不同路径
目录
题目描述
题意分析
机器人站在
m x n网格的左上角，每一步只能向右或向下移动一格，问走到右下角一共有多少条不同的路径。要求的是「路径条数」，不需要列出每条路径长什么样，这是一个纯计数问题。移动规则给出了一个很强的信号：只能向右或向下，意味着机器人永远不会走回头路，每条路径恰好走
m + n - 2步，其中向下m - 1步、向右n - 1步，只是先后顺序不同。约束上
m和n都在 1 到 100 之间，且题目保证答案不超过int范围，所以计数本身不必担心溢出。边界情况是m = 1或n = 1：只有一行或一列时，机器人只能一路走到底，答案就是 1。
解法：一维动态规划
核心思路
最直接的暴力做法是从起点出发递归枚举每一步向右还是向下，走到终点就计数加一。但路径总数是指数级的（本质上是 $C(m+n-2, m-1)$ 条），而且递归树里大量子问题被反复计算——比如从
(2, 2)走到终点的方案数，会被所有能到达(2, 2)的路径各算一遍。瓶颈就在重复子问题上。关键观察是：到达格子
(i, j)的最后一步只有两种可能——从上方(i - 1, j)走下来，或从左侧(i, j - 1)走过来，且两类路径互不重叠。于是定义状态：dp[i][j]表示从起点走到(i, j)的不同路径数，转移方程为dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。第一行和第一列的格子只能一路向右或一路向下到达，路径数全为 1，这就是递推的初始条件。由于每一行只依赖上一行，可以把二维压缩成一维：
dp[j]表示当前正在计算的这一行中，第j列的路径数。从左到右更新时，dp[j]在赋值前保存的是上一行的值（上方来的路径数），dp[j - 1]已经是本行的新值（左侧来的路径数），所以dp[j] += dp[j - 1]一句话就完成了转移。面试如果追问更优解法：答案就是在
m + n - 2步中选出m - 1步向下的方案数，直接算组合数 $C(m+n-2, m-1)$ 即可做到 $O(m + n)$ 时间，一句话带过就好。
解题步骤
- 创建长度为
n的一维数组dp，全部初始化为 1。为什么：第一行每个格子都只能从左边一路走来，路径数都是 1，这一步等价于算好了第一行。- 外层循环
i从 1 到m - 1，逐行递推。为什么：第一行已经在初始化中处理完毕，从第二行开始才需要转移。- 内层循环
j从 1 到n - 1，从左到右更新。为什么：每行第 0 列永远是 1 不用动；从左到右保证dp[j - 1]已经是本行的新值、dp[j]还是上一行的旧值，恰好对应「左 + 上」。- 执行
dp[j] += dp[j - 1]。为什么：这就是转移方程dp[i][j] = dp[i - 1][j] + dp[i][j - 1]的一维形式。- 循环结束后返回
dp[n - 1]。为什么：此时dp保存的是最后一行的状态，末尾元素就是右下角的路径数。- 以
m = 3, n = 3走一遍：初始化dp = [1, 1, 1]（第一行）。第二行：j = 1时dp[1] = 1 + 1 = 2，j = 2时dp[2] = 1 + 2 = 3，得dp = [1, 2, 3]。第三行：j = 1时dp[1] = 2 + 1 = 3，j = 2时dp[2] = 3 + 3 = 6，得dp = [1, 3, 6]。返回dp[2] = 6，与 3×3 网格的正确答案一致。
代码实现
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)$，滚动数组只保留一行状态，代替了完整的 $m \times n$ 二维表。
关键点总结
- 计数型网格 DP 的通用套路：分析「到达当前状态的最后一步来自哪里」，把互不重叠的来源加起来，这个拆分思路可以迁移到几乎所有路径计数题。
- 初始条件要覆盖「无法用转移方程表达」的状态：首行首列只有一种走法，直接置 1，而不是套转移公式。
- 二维压一维的判断标准：转移只依赖上一行和本行左侧时就能滚动，更新方向必须保证「被依赖的新值已算好、被依赖的旧值未覆盖」，本题是从左到右。
- 面试视角：先给出二维 DP 讲清状态定义，再主动压缩到一维展示空间优化意识；如果面试官追问数学解，报出 $C(m+n-2, m-1)$ 并说明是「在总步数里选向下的步」即可，这是常见的加分项。
- 写 DP 前先手算一个小规模用例（如 3×3 = 6），能在白板上快速验证转移方程和初始化是否正确。
易错点总结
- 错误写法：
new int[n]之后忘记Arrays.fill(dp, 1)：用例m = 3, n = 3→ 数组全 0，转移全程加 0，返回 0。- 错误写法：外层循环从
i = 0开始：用例m = 3, n = 3→ 第一行被多算一轮变成前缀和，最终返回 10 而不是 6。- 错误写法：内层循环从
j = 0开始：任意用例 → 访问dp[j - 1]即dp[-1]，数组下标越界直接抛异常。- 错误写法：内层从右往左更新
for (int j = n - 1; j >= 1; j--)：用例m = 3, n = 3→dp[j - 1]取到的是上一行旧值，漏算左侧路径，返回 4 而不是 6。- 错误写法：转移写成
dp[j] = dp[j - 1]漏加上方：用例m = 3, n = 3→ 每行都退化成全 1，返回 1。- 错误写法：纯递归
f(i, j) = f(i - 1, j) + f(i, j - 1)不加记忆化：用例m = 100, n = 100→ 子问题被指数级重复计算，超时。- 错误写法：数学解用
int连乘分子再除阶乘：用例m = 10, n = 10→ 分子中间乘积溢出int，结果为负数或错误值，应边乘边除并用long。- 错误写法：组合数写成 $C(m+n, m)$：用例
m = 3, n = 7→ 把格子数当成步数，返回 120，正确答案是 $C(8, 2) = 28$。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 63. 不同路径 II | 中等 | 加入障碍物，障碍格路径数强制置 0 |
| 64. 最小路径和 | 中等 | 计数换成求和最小，加法变取小 |
| 120. 三角形最小路径和 | 中等 | 三角形网格，自底向上递推更简洁 |
| 174. 地下城游戏 | 困难 | 反向 DP，从终点倒推最低初始血量 |
| 688. 骑士在棋盘上的概率 | 中等 | 概率型网格 DP，八方向转移带步数维度 |
| 931. 下降路径最小和 | 中等 | 允许斜向移动，三个来源取最小 |
| 980. 不同路径 III | 困难 | 必须踩遍所有空格，只能回溯枚举 |
| 1289. 下降路径最小和 II | 困难 | 需维护上一行最小与次小值优化转移 |
| 1301. 最大得分的路径数目 | 困难 | 最优值与方案数两个状态同时递推 |
| 1594. 矩阵的最大非负积 | 中等 | 有负数时需同时维护最大与最小乘积 |
| LCR 099. 最小路径和 | 中等 | 64 的镜像题 |
| LCR 100. 三角形最小路径和 | 中等 | 120 的镜像题 |
| 剑指 Offer 47. 礼物的最大价值 | 中等 | 求最大收益版本的同结构网格 DP |