62 不同路径

一、题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

二、题解

思路：动态规划

1. 定义状态（State）： 定义一个二维数组 dp，其中 dp[i][j] 表示机器人从起点 (0, 0) 到达网格中坐标 (i, j) 的不同路径总数。

2. 状态转移方程（Transition）：因为机器人每次只能向下或向右移动一步，所以要到达当前格子 (i, j)，它只能从：

   • 上方的格子 (i-1, j) 向下一步走过来。
   • 左方的格子 (i, j-1) 向右一步走过来。 因此，到达当前格子的路径总数，就是到达它上方格子的路径数与到达它左方格子的路径数之和。 公式为：$dp[i][j] = dp[i-1][j] + dp[i][j-1]$

3. 初始化（Base Case）：

   • 第一行： 机器人要到达第一行的任何一个格子，只能一直向右走，只有 $1$ 条路径。因此 dp[0][j] = 1。
   • 第一列： 机器人要到达第一列的任何一个格子，只能一直向下走，只有 $1$ 条路径。因此 dp[i][0] = 1。

4. **遍历顺序：从左到右，从上到下遍历整个网格即可。

class Solution {
    public int uniquePaths(int m, int n) {
        // 1. 定义 dp 数组
        int[][] dp = new int[m][n];

        // 2. 初始化第一列（只能向下走，路径数为1）
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        // 3. 初始化第一行（只能向右走，路径数为1）
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        // 4. 从左到右，从上到下推导状态
        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];
            }
        }

        // 5. 返回到达右下角的路径数
        return dp[m - 1][n - 1];
    }
}

时间复杂度：$O(m \times n)$

空间复杂度：$O(m \times n)$