62. 不同路径

问题描述

一个机器人位于一个 m x n 网格的左上角（起始点标记为 “Start”）。机器人每次只能向下或向右移动一步。机器人试图达到网格的右下角（标记为 “Finish”）。计算从左上角到右下角有多少条不同的路径。

示例：

输入: m = 3, n = 7
输出: 28

输入: m = 3, n = 2
输出: 3
解释:
从左上角到右下角共有 3 条路径：
1. 右 → 下 → 下
2. 下 → 下 → 右
3. 下 → 右 → 下

算法思路

动态规划（DP 数组）：

1. 状态定义：dp[i][j] 表示从起点 (0,0) 到达网格 (i,j) 的路径数量。
2. 状态转移：
   • 机器人只能从上方或左方到达当前位置：
     dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. 初始化：
   • 第一行所有位置：只有一种路径（一直向右），dp[0][j] = 1
   • 第一列所有位置：只有一种路径（一直向下），dp[i][0] = 1
4. 遍历顺序：
   • 按行遍历（i 从 1 到 m-1），每行内按列遍历（j 从 1 到 n-1）

空间优化（一维 DP）：

• 由于每行状态只依赖上一行和当前行的左侧状态，可用一维数组滚动更新：
  • dp[j] = dp[j]（上一行同列） + dp[j-1]（当前行左列）
• 每行遍历前需保留左侧第一个元素不变（保持第一列初始值 1）

代码实现

方法一：动态规划（DP 数组）

class Solution {
    public int uniquePaths(int m, int n) {
        // dp[i][j]：到达 (i,j) 的路径数
        int[][] dp = new int[m][n];
        
        // 初始化第一行和第一列
        for (int j = 0; j < n; j++) dp[0][j] = 1; // 第一行：只能向右
        for (int i = 0; i < m; i++) dp[i][0] = 1; // 第一列：只能向下
        
        // 从 (1,1) 开始填充 DP 表
        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]; // 返回终点结果
    }
}

方法二：动态规划（空间优化）

class Solution {
    public int uniquePaths(int m, int n) {
        // dp[j] 表示当前行到达第 j 列的路径数
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // 初始化第一行：全为 1
        
        // 从第二行开始更新
        for (int i = 1; i < m; i++) {
            // 每行第一个位置保持为 1（第一列特性）
            for (int j = 1; j < n; j++) {
                // 状态转移：dp[j]（上一行同列） + dp[j-1]（当前行左列）
                dp[j] = dp[j] + dp[j-1];
            }
        }
        return dp[n-1]; // 返回最后一列结果
    }
}

算法分析

• 时间复杂度：O(m × n)
  需遍历整个网格。
• 空间复杂度：
  • 二维 DP：O(m × n)
  • 一维 DP：O(n)

算法过程

m=3, n=2

1. 初始化二维 DP 表：

   [1, 1]
   [1, 0]
   [1, 0]
   

2. 状态转移：
   • i=1, j=1：dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
   • i=2, j=1：dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
3. 结果：dp[2][1] = 3

测试用例

public static void main(String[] args) {
    Solution solution = new Solution();
    
    // 测试用例1: 标准示例
    System.out.println(solution.uniquePaths(3, 7)); // 28
    
    // 测试用例2: 矩形网格
    System.out.println(solution.uniquePaths(3, 2)); // 3
    
    // 测试用例3: 单行网格
    System.out.println(solution.uniquePaths(1, 5)); // 1
    
    // 测试用例4: 单列网格
    System.out.println(solution.uniquePaths(5, 1)); // 1
    
    // 测试用例5: 最小网格
    System.out.println(solution.uniquePaths(1, 1)); // 1
}

关键点

1. 状态转移逻辑：
   路径数 = 上方路径数 + 左方路径数
2. 初始化意义：
   • 第一行：只能向右走，路径数均为 1
   • 第一列：只能向下走，路径数均为 1
3. 空间优化核心：
   • 一维数组 dp[j] 同时承载上一行和当前行状态
   • 内层循环从左向右更新（确保 dp[j-1] 是当前行已更新值）

常见问题

1. 为什么第一行和第一列初始化为 1？
   这些位置只有唯一路径（直线向右或向下）。
2. 空间优化中为何从左向右遍历？
   确保计算 dp[j] 时，dp[j-1] 已是当前行更新后的值（左列状态）。
3. 如何处理边界情况？
   • 单行/单列网格：直接返回 1
   • 1×1 网格：起点即终点，返回 1