不同路径
Unique Paths
在一个 m × n 的网格中，从左上角走到右下角，每次只能向下或向右，求不同路径数。
在力扣中练习题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28
示例 2：
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3 输出：28
示例 4：
输入：m = 3, n = 3 输出：6
提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 109
解题思路
二维 DP · 上方 + 左方
到达每格的路径数，等于上方和左方路径数之和
暴力枚举每条路径会指数爆炸。换个角度：到达格子 (i,j) 的最后一步只有两种可能——从上面下来，或者从左边过来。
所以到达 (i,j) 的路径数，就是这两个格子的路径数相加：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
边界：第一行只能一直向右走，第一列只能一直向下走，路径数都为 1。
自拟主例 m = 3, n = 4。第一行内部格子只有左方来源；进入第二行后，每格开始同时接收上方和左方。右下角的 10 来自上方 4 和左方 6。
(1,1)：从上方来有 1 条，从左方来有 1 条，共 2 条。
- i
- 1
- j
- 1
dp[i][j]：从左上角走到 (i,j) 的路径数；每一步只能向下或向右
dp[1][1]=dp[0][1] + dp[1][0]1 + 1=2(2,2)：从上方来有 3 条，从左方来有 3 条，共 6 条。
- i
- 2
- j
- 2
dp[i][j]：从左上角走到 (i,j) 的路径数；每一步只能向下或向右
dp[2][2]=dp[1][2] + dp[2][1]3 + 3=6按行从左到右填表，计算 (i,j) 时上方和左方都已经确定。时间 O(m × n)，空间 O(m × n)。
易错点
- 边界只初始化第一行，漏掉第一列：第二行第一格会从 0 开始，后面全错。
- 把加法写成 max：路径数是累加，不是取最优。
- m 或 n 为 1：循环不进入，必须靠边界初始化直接返回 1。
滚动数组 · 一维 DP
一行一行往下滚，dp[j] 覆盖前就是上方值
时间相同，空间从 O(m × n) 降到 O(n)；代价是只保留上一行，不能直接还原具体路径。
转移只依赖上一行和本行左边，所以可以只保留一行。
dp[j] 在更新前是上方的路径数，更新后是本行的路径数；左边的 dp[j-1] 已经在本次行内更新过，正好是左方的值。于是
dp[j] = dp[j] + dp[j-1]
第一行全部初始化为 1；之后每行从 j=1 开始向右更新。
时间 O(m × n)，空间 O(n)。如果题目要求输出具体路径，就不能只留一行，需要额外记录选择。
- 1dp 长度为 n，全部初始化为 1（第一行）。
- 2i 从 1 枚举到 m-1。
- 3j 从 1 枚举到 n-1：dp[j] += dp[j-1]。
- 4返回 dp[n-1]。
易错点
- j 从 0 开始：dp[0] 会被加两次，第一列不再是 1。
- 更新顺序从右往左：dp[j-1] 还是上一行的值，左方来源就丢了。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
m = 3, n = 4第一行只能一直向右走，第一列只能一直向下走，路径数都是 1。
- m × n
- 3 × 4
dp[i][j]：从左上角走到 (i,j) 的路径数；每一步只能向下或向右
dp[0][0]=1查看 C++ 代码
延伸阅读
- 不同路径 II（63）在格子里加了障碍：遇到障碍时 dp 直接置 0，转移形式不变。
- 这也是组合数问题：从 (0,0) 到 (m-1,n-1) 要走 m+n-2 步，其中选 m-1 步向下，答案是 C(m+n-2, m-1)。