本文概览：本文讲解不同路径的核心思路：只能向下或向右移动时，到达每个格子的路径数等于其上方和左方路径数之和，用动态规划递推；方法一是二维 dp 数组，方法二是只保留上一行的一维数组把空间降到 O(n)

---

一、题目

---

二、题目分析

1. 题目要求

一个机器人位于一个 m × n 网格的左上角（起点记为 (0, 0)）。机器人每次只能向下或者向右移动一步，要走到网格的右下角（终点记为 (m-1, n-1)）。问总共有多少条不同的路径。

示例 1：m = 3, n = 7 → 28

示例 2：m = 3, n = 2 → 3（向右 → 向下 → 向下；向下 → 向右 → 向下；向下 → 向下 → 向右）

2. 怎么想这题？

看到"从起点走到终点"，第一反应很容易想到 DFS 或 BFS。确实能做——沿着每条路一步步试探。但这里的关键要落在题目问的是什么上：它问的不是"能不能到终点"，而是"有几条路能到终点"。

如果只是找一条路，DFS 走通一条就返回，完全没问题；可要数"全部"路径，就相当于把每条到达终点的路径都枚举一遍。网格越大，路径数按组合数级别爆炸增长，递归深度也跟着拉满，栈很容易溢出。

这条路走不通，换个角度往回看。既然机器人每一步只能向下或向右，那么反过来想：终点 (i, j) 只能由它上面的格子 (i-1, j) 或者它左边的格子 (i, j-1) 走一步到达，没有第三条来路。所以"到达终点的路径数"就等于"到达它上面格子的路径数"加上"到达它左边格子的路径数"。

这个式子对终点的上一格、上上格同样成立，一路往前推，推到起点为止。大问题的答案由两个更小的同类问题的答案加起来，这是典型的动态规划。

3. 需要解决哪几个问题？

方向定了用 DP，动手前先想清楚三件事：

问题一：状态怎么定义？dp[i][j] 表示什么？

问题二：转移方程怎么写？到达 (i, j) 的路径数，由哪几个已知的格子推出来？

问题三：第一行和第一列怎么办？它们没有"上方格子"或"左方格子"，转移方程对这些位置会失效。

---

三、方法一：二维 DP 数组，O(m × n) 空间

1. 思路概览

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    // 第一列：只能一路向下，每条只有一条路径
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    // 第一行：只能一路向右，每条只有一条路径
    for (int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

思路简要说明：

1. 状态定义：dp[i][j] 表示从起点 (0,0) 走到 (i,j) 的路径总数
2. 转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]，上方格子的路径数加左方格子的路径数
3. 初始化：第一行和第一列全部置 1（它们各自只有一条路径）
4. 遍历顺序：按行从上到下、每行从左到右，保证算 (i,j) 时上方和左方都先算好
5. 时间复杂度 O(m × n)，空间 O(m × n)

2. 思路详解

第一步：解决状态定义——dp[i][j] 表示什么？

题目要的是"从起点到终点的路径条数"。顺着"倒推"的思路，每个格子都有自己的"到达路径数"，起点 (0,0) 是 1 条（不动也算一种）。所以直接把状态定义在每个格子上：

dp[i][j] = 从起点走到格子 (i, j) 的不同路径条数。

终点就是 dp[m-1][n-1]，算出来就是答案。

第二步：解决转移方程——到达 (i,j) 只能从哪来？

机器人只能向下或向右，所以能一步到达 (i, j) 的只有两个来源：

• 从它上面的格子 (i-1, j) 向下走一步，贡献 dp[i-1][j] 条路径
• 从它左边的格子 (i, j-1) 向右走一步，贡献 dp[i][j-1] 条路径

两批路径互不重叠（最后一步一个是向下、一个是向右），总数直接相加：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

这就是转移方程。

第三步：解决边界——第一行和第一列为什么都是 1？

转移方程要读 dp[i-1][j] 和 dp[i][j-1]，但第一行（i = 0）没有上方格子，第一列（j = 0）没有左方格子，方程对它们失效。所以边界得单独定：

• 第一行：只能一路向右走，从 (0,0) 到 (0,j) 只有唯一一种走法，所以 dp[0][j] = 1。
• 第一列：只能一路向下走，从 (0,0) 到 (i,0) 也只有唯一一种走法，所以 dp[i][0] = 1。

这两个循环把边界填好，内部格子就能套转移方程了。

第四步：完整执行过程（m=3, n=3）

以 3 × 3 网格为例，终点答案是 6：

初始化第一行、第一列为 1：

    0  1  2
0 [ 1  1  1 ]
1 [ 1  .  . ]
2 [ 1  .  . ]

i=1, j=1：dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
i=1, j=2：dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3

    0  1  2
0 [ 1  1  1 ]
1 [ 1  2  3 ]
2 [ 1  .  . ]

i=2, j=1：dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
i=2, j=2：dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6

    0  1  2
0 [ 1  1  1 ]
1 [ 1  2  3 ]
2 [ 1  3  6 ]

返回 dp[2][2] = 6 ✓

每一步都只依赖它正上方和正左方已经填好的值，按行扫一遍就能把整张表填满。

3. 复杂度分析

时间复杂度 O(m × n)：每个格子计算一次，常数次运算。

空间复杂度 O(m × n)：需要一张完整的二维 dp 表。

---

四、二维数组能不能压成一维？

回头看转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]，它只依赖两个值：正上方 dp[i-1][j] 和正左方 dp[i][j-1]。

算完第 i 行之后，第 i-1 行及更早的行就再也不被用到了。真正需要的只有"当前行"和"上一行"两行信息。进一步想，算 dp[i][j] 时，左方 dp[i][j-1] 已经在这一轮算出来了，上方 dp[i-1][j] 还呆在上一行的位置上。

那能不能只用一个一维数组，边算边原地覆盖，把"上一行"和"当前行"叠进同一个数组里？

---

五、方法二：滚动一维数组，O(n) 空间

1. 思路概览

public int uniquePaths(int m, int n) {
    int[] row = new int[n];
    Arrays.fill(row, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            row[j] += row[j - 1];
        }
    }
    return row[n - 1];
}

思路简要说明：

1. 状态定义：row[j] 表示当前行第 j 列的路径数，随行滚动更新
2. 初始化：row 全部填 1，正好是"第一行"的值
3. 转移：row[j] += row[j-1]，左边是刚算好的本行左方值，当前位置是还没被覆盖的上一行同列值（上方值）
4. 返回：row[n-1] 就是滚到最后一行最右端的答案
5. 时间复杂度 O(m × n)，空间 O(n)

2. 思路详解

第一步：初始化为什么全填 1？

一维的 row 对应二维表里的"当前行"。循环从 i = 1（第二行）开始，所以进来之前 row 先得装好第一行的状态——第一行每个格子路径数都是 1，Arrays.fill(row, 1) 正好一步到位。

第二步：row[j] += row[j-1] 到底在算什么？

这一行是优化后最关键的地方。当往后推第 i 行时，row 上同时躺着两层信息：

• row[j] 此刻还是上一行同列 dp[i-1][j] 的值，也就是"上方"的那份；
• row[j-1] 已经在本轮回被更新成本行左方 dp[i][j-1] 的值，也就是"左方"的那份。

所以 row[j] += row[j-1] 做的事和 dp[i][j] = dp[i-1][j] + dp[i][j-1] 一模一样：把"上方"和"左方"加到一起，写回 row[j]。只是"上方值"在加完这一下之后就被覆盖了，数组里只留最新的一行，空间因此省下了一整个维度。

至于 row[0] 从来不进内层循环（j 从 1 开始），它永远是初始的 1——正好满足第一列每个格子都是 1 的边界。

第三步：完整执行过程（m=3, n=3）

初始 row = [1, 1, 1]      ← 第一行

i=1（第二行）：
  j=1：row[1] = row[1] + row[0] = 1 + 1 = 2   → [1, 2, 1]
  j=2：row[2] = row[2] + row[1] = 1 + 2 = 3   → [1, 2, 3]

i=2（第三行）：
  j=1：row[1] = row[1] + row[0] = 2 + 1 = 3   → [1, 3, 3]
  j=2：row[2] = row[2] + row[1] = 3 + 3 = 6   → [1, 3, 6]

返回 row[2] = 6 ✓

对比方法一的二维表，row 在每一轮结束时的取值，正是那张表对应的行：

方法一逐行结果：          row 滚动结果：
[1, 1, 1]（第一行）  →   [1, 1, 1]
[1, 2, 3]（第二行）  →   [1, 2, 3]
[1, 3, 6]（第三行）  →   [1, 3, 6]

滚到最后一行，row[n-1] 就是终点的路径数。

3. 复杂度分析

时间复杂度 O(m × n)：两层循环规模不变。

空间复杂度 O(n)：只保留一行，从 O(m × n) 降到 O(n)。

---

六、总结

维度	方法一 二维 DP	方法二 一维滚动
状态	dp[i][j] 全部格子	row[j] 只保留当前行
空间	O(m × n)	O(n)
时间	O(m × n)	O(m × n)
关键点	第一行第一列初始化 1	原地叠加，上方值在覆盖前被用掉

两种方法源自同一个想法：到达每个格子的路径数，等于它上方和左方路径数之和。方法一老老实实用一张二维表存下每个格子的答案；方法二发现算下一行时上一行就作废了，于是把两行塞进同一个数组，靠"先读上方旧值、再加左方新值"的原地更新，把空间从 O(m × n) 压到 O(n)。

这道题的核心倒不在于代码多复杂，而在于想通"为什么能用 DP"：机器人只能向下向右，决定了每一个格子的来路只有上方和左方两处，路径数天然可以拆成两个更小的同类之和——这和之前见过的"题目分析 → 找转移方程"的推导路径是一致的。