一、题目描述

一个机器人位于 m × n 网格的左上角，需要移动到网格的右下角。机器人每次只能执行以下两种操作之一：

• 向右移动一格；

• 向下移动一格。

请计算机器人从左上角到达右下角一共有多少条不同路径。

例如：

输入：m = 3，n = 7
输出：28

输入：m = 3，n = 2
输出：3

对于 3 × 2 的网格，机器人需要向右一次、向下两次。三种不同移动顺序分别是：

右 → 下 → 下
下 → 右 → 下
下 → 下 → 右

因此最终答案为 3。

---

二、为什么使用动态规划？

假设机器人要到达网格中的某个位置。由于机器人只能向右或向下移动，所以进入这个位置前，它只可能位于：

1. 当前格子的上方，然后向下走一步；

2. 当前格子的左方，然后向右走一步。

也就是说，到达当前位置的路径可以拆成两个规模更小的问题：

• 到达上方格子有多少条路径；

• 到达左方格子有多少条路径。

这些结果在后续计算中会被反复使用，因此可以把它们保存到数组中，避免重复计算。这正是动态规划的基本思想。

---

三、定义动态规划状态

定义：

dp[i][j]：从左上角出发，到达第 i 行、第 j 列的路径数量

这里采用与截图一致的 1 开始下标：

• 左上角是 dp[1][1]；

• 右下角是 dp[m][n]；

• 最终答案是 dp[m][n]。

为了能够直接使用 1 到 m、1 到 n 的下标，数组长度需要多申请一行和一列：

int[][] dp = new int[m + 1][n + 1];

数组下标为 0 的行和列不会参与实际状态计算，只用于简化下标理解。

---

四、初始化第一行和第一列

动态规划必须先确定边界状态。

1. 初始化第一行

机器人位于第一行时不能继续向上或向下绕行，只能从左上角一直向右走。因此，到达第一行任意格子都只有一条路径：

for (int j = 1; j <= n; j++) {
    dp[1][j] = 1;
}

即：

dp[1][1] = 1
dp[1][2] = 1
dp[1][3] = 1
...
dp[1][n] = 1

2. 初始化第一列

同理，机器人到达第一列中的任意格子时，只能从左上角一直向下走，因此路径数量也都是 1：

for (int i = 1; i <= m; i++) {
    dp[i][1] = 1;
}

虽然 dp[1][1] 会被赋值两次，但两次结果都是 1，不会影响答案。

初始化完成后，3 × 7 网格的 DP 数组有效区域如下：

dp	第1列	第2列	第3列	第4列	第5列	第6列	第7列
第1行	1	1	1	1	1	1	1
第2行	1	0	0	0	0	0	0
第3行	1	0	0	0	0	0	0

---

五、推导状态转移公式

对于既不在第一行、也不在第一列的位置 dp[i][j]，机器人只可能从两个方向进入。

1. 从上方到达

上方格子的位置是：

dp[i - 1][j]

到达上方格子的每一条路径，都可以再向下走一步，到达当前位置。因此，这部分贡献了 dp[i - 1][j] 条路径。

2. 从左方到达

左方格子的位置是：

dp[i][j - 1]

到达左方格子的每一条路径，都可以再向右走一步，到达当前位置。因此，这部分贡献了 dp[i][j - 1] 条路径。

两类路径最后一步的方向不同，不会发生重复，所以将它们直接相加：

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

这就是本题最核心的状态转移公式。

可以简单记成：

当前格子的路径数 = 上方格子的路径数 + 左方格子的路径数。

---

六、以 m = 3、n = 7 为例推演

初始化第一行和第一列后，从第 2 行、第 2 列开始计算。

1. 计算第二行

dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2
dp[2][3] = dp[1][3] + dp[2][2] = 1 + 2 = 3
dp[2][4] = dp[1][4] + dp[2][3] = 1 + 3 = 4

继续计算，可以得到第二行：

1  2  3  4  5  6  7

2. 计算第三行

dp[3][2] = dp[2][2] + dp[3][1] = 2 + 1 = 3
dp[3][3] = dp[2][3] + dp[3][2] = 3 + 3 = 6
dp[3][4] = dp[2][4] + dp[3][3] = 4 + 6 = 10

最终完整 DP 表为：

dp	第1列	第2列	第3列	第4列	第5列	第6列	第7列
第1行	1	1	1	1	1	1	1
第2行	1	2	3	4	5	6	7
第3行	1	3	6	10	15	21	28

因此：

dp[3][7] = 28

从左上角到右下角一共有 28 条不同路径。

---

七、Java 完整代码

class Solution {

    public int uniquePaths(int m, int n) {
        // dp[i][j] 表示到达第 i 行、第 j 列的路径数量
        int[][] dp = new int[m + 1][n + 1];

        // 第一行只能一直向右走，路径数均为 1
        for (int j = 1; j <= n; j++) {
            dp[1][j] = 1;
        }

        // 第一列只能一直向下走，路径数均为 1
        for (int i = 1; i <= m; i++) {
            dp[i][1] = 1;
        }

        // 从第 2 行、第 2 列开始计算其他位置
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m][n];
    }
}

代码执行顺序是：

1. 创建 m + 1 行、n + 1 列的二维数组；

2. 将第一行初始化为 1；

3. 将第一列初始化为 1；

4. 从左到右、从上到下填写剩余格子；

5. 返回右下角的 dp[m][n]。

---

八、为什么必须从左上向右下遍历？

计算 dp[i][j] 时，需要提前知道：

dp[i - 1][j]  // 上方状态
dp[i][j - 1]  // 左方状态

因此，遍历到当前位置之前，上方和左方必须已经计算完成。从第 2 行、第 2 列开始，按行从左到右填写，正好满足这个依赖关系。

如果随意改变遍历方向，就可能在前置状态尚未计算时读取默认值 0，导致结果错误。

---

九、复杂度分析

时间复杂度

两层循环遍历整个 m × n 网格，每个位置只计算一次，因此时间复杂度为：

O(m × n)

空间复杂度

使用了一个 m + 1 行、n + 1 列的二维数组，因此空间复杂度为：

O(m × n)