LeetCode 62. 不同路径
目录
题目描述
✅ 62. 不同路径
题意分析
机器人站在
m x n网格的左上角，每一步只能向右或向下移动一格，问走到右下角一共有多少条不同的路径。要求的是「路径条数」，不需要列出每条路径长什么样，这是一个纯计数问题。移动规则给出了一个很强的信号：只能向右或向下，意味着机器人永远不会走回头路，每条路径恰好走
m + n - 2步，其中向下m - 1步、向右n - 1步，只是先后顺序不同。约束上
m和n都在 1 到 100 之间，且题目保证答案不超过int范围，所以计数本身不必担心溢出。边界情况是m = 1或n = 1：只有一行或一列时，机器人只能一路走到底，答案就是 1。
解法：一维动态规划
核心思路
问题关键：到达
(i, j)的最后一步只可能来自上方或左侧，两类路径互不重叠，因此路径数可以相加：paths(i, j) = paths(i - 1, j) + paths(i, j - 1)。为什么选动态规划：暴力递归会反复计算同一个格子的路径数；DP 按行计算，每个格子只处理一次。完整二维表没有必要，因为当前行只依赖上一行和本行左侧，所以用一维数组即可。
状态与不变量：处理第
i行第j列前，dp[j]是上方格子的路径数，dp[j - 1]是左侧格子的路径数；更新dp[j] += dp[j - 1]后，dp[j]就变成当前格子的路径数。dp[0] = 1表示每一行的第一列始终只有一种走法。组合数学也能得到 $C(m+n-2, m-1)$，但要处理乘除顺序和中间溢出；面试主解优先写更直观、稳定的一维 DP。
解题步骤
- 创建长度为
n的dp，只令dp[0] = 1。- 从第 0 行开始逐行扫描；每行从第 1 列开始，执行
dp[j] += dp[j - 1]。- 必须从左向右更新，才能同时取得“上一行的旧
dp[j]”和“本行的新dp[j - 1]”。- 扫描结束后，
dp[n - 1]就是右下角的路径数。以
m = 3, n = 3为例，dp依次变为[1,1,1] → [1,2,3] → [1,3,6]，答案为 6。
代码实现
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)$，只保留一行状态；也可以让较短的边作为列，将其优化为 $O(\min(m,n))$。
关键点总结
- 先用“最后一步来自上或左”证明转移，再写代码，正确性最容易讲清楚。
- 一维压缩后的更新方向是核心：
dp[j]保留上方，dp[j - 1]已更新为左侧。dp[0] = 1同时完成起点和第一列初始化，单行、单列都无需特判。- 追问组合数学时，说明总步数为
m+n-2，从中选择m-1次向下即可。
易错点总结
dp全部保持默认值 0：m=3,n=3会得到 0；必须令dp[0] = 1。- 从右向左更新：会读到上一行的
dp[j - 1]，破坏“左侧已更新”的不变量；按本文初始化方式，3×3会算成 3 而不是 6。- 内层从
j = 0开始：访问dp[-1]越界，第一列本来就不需要转移。- 组合数直接用
int计算阶乘：最终答案即使不溢出，中间乘积也可能溢出；需要long并边乘边除。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 63. 不同路径 II | 中等 | 加入障碍物，障碍格路径数强制置 0 |
| 64. 最小路径和 | 中等 | 计数换成求和最小，加法变取小 |
| 120. 三角形最小路径和 | 中等 | 三角形网格，自底向上递推更简洁 |
| 174. 地下城游戏 | 困难 | 反向 DP，从终点倒推最低初始血量 |
| 688. 骑士在棋盘上的概率 | 中等 | 概率型网格 DP，八方向转移带步数维度 |
| 931. 下降路径最小和 | 中等 | 允许斜向移动，三个来源取最小 |
| 980. 不同路径 III | 困难 | 必须踩遍所有空格，只能回溯枚举 |
| 1289. 下降路径最小和 II | 困难 | 需维护上一行最小与次小值优化转移 |
| 1301. 最大得分的路径数目 | 困难 | 最优值与方案数两个状态同时递推 |
| 1594. 矩阵的最大非负积 | 中等 | 有负数时需同时维护最大与最小乘积 |
| LCR 098. 不同路径 | 中等 | 本题镜像题 |
| LCR 099. 最小路径和 | 中等 | 64 的镜像题 |
| LCR 100. 三角形最小路径和 | 中等 | 120 的镜像题 |
| 剑指 Offer 47. 礼物的最大价值 | 中等 | 求最大收益版本的同结构网格 DP |