问题简介

🔗 LeetCode 62. 不同路径

📝 题目描述

一个机器人位于一个 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

---

💡 解题思路

✅ 方法一：动态规划（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. 最终答案：dp[m-1][n-1]

时间复杂度低，空间可优化。

---

✅ 方法二：空间优化的动态规划

观察发现：计算当前行只需要上一行的数据。

• 使用一维数组 dp[n] 即可。
• 每次更新：dp[j] += dp[j-1]（因为 dp[j] 原本是上一行的值，dp[j-1] 是当前行左边的值）

---

✅ 方法三：组合数学（数学公式）

从 (0,0) 到 (m-1,n-1)，总共要走 (m-1) + (n-1) = m+n-2 步。

其中必须选择 m-1 步向下（其余自动为向右），或等价地选 n-1 步向右。

因此路径总数为组合数：

$$\begin{gathered} C\_{m+n-2}^{m-1}= \\ frac(m+n-2)!(m-1)!(n-1)! \end{gathered}$$

注意防止整数溢出，需边乘边除。

---

💻 代码实现

// 方法一：二维 DP
class Solution {
    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];
    }
}

// 方法二：一维 DP（空间优化）
class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j-1];
            }
        }
        return dp[n-1];
    }
}

// 方法三：组合数学
class Solution {
    public int uniquePaths(int m, int n) {
        long ans = 1;
        int total = m + n - 2;
        int k = Math.min(m - 1, n - 1); // 选较小的，减少计算
        
        for (int i = 0; i < k; i++) {
            ans = ans * (total - i) / (i + 1);
        }
        return (int) ans;
    }
}

// 方法一：二维 DP
func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    
    for i := 0; i < m; i++ {
        dp[i][0] = 1
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1
    }
    
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}

// 方法二：一维 DP（空间优化）
func uniquePaths(m int, n int) int {
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }
    
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[j] += dp[j-1]
        }
    }
    return dp[n-1]
}

// 方法三：组合数学
func uniquePaths(m int, n int) int {
    total := m + n - 2
    k := min(m-1, n-1)
    var ans int64 = 1
    
    for i := 0; i < k; i++ {
        ans = ans * int64(total - i) / int64(i + 1)
    }
    return int(ans)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

---

🎯 示例演示

以 m=3, n=2 为例：

步骤	dp 数组（一维）
初始化	[1, 1]
i=1（第二行）	j=1: dp[1] = dp[1] + dp[0] = 1 + 1 = 2 → [1, 2]
i=2（第三行）	j=1: dp[1] = 2 + 1 = 3 → [1, 3]

✅ 最终结果：dp[1] = 3，符合预期。

---

✅ 答案有效性证明

• 动态规划正确性：基于最优子结构和无后效性。每个位置的路径数仅依赖于其上方和左方，且一旦确定不再改变。
• 组合数学正确性：每条路径由固定数量的“下”和“右”组成，顺序不同即为不同路径，本质是排列组合中的多重集排列问题，等价于从 m+n-2 步中选 m-1 步向下。

两种方法在数学上等价，可通过小规模枚举验证一致性。

---

📊 复杂度分析

方法	时间复杂度	空间复杂度
二维 DP	$O(mn)$	$O(mn)$
一维 DP	$O(mn)$	$O(n)$
组合数学	$$\begin{gathered} O( \\ min(m,n)) \end{gathered}$$	$O(1)$

💡 推荐使用组合数学法（效率最高）或一维 DP（易理解且空间优）。

---

📌 问题总结

• 本题是经典的网格路径计数问题，核心在于识别只能向右/向下带来的无环、单向依赖特性。
• 动态规划是通用解法，适用于带障碍物等变种（如 LeetCode 63）。
• 组合数学提供最优解，但需注意整数溢出和除法顺序（必须先乘后除，且保证整除）。
• 空间优化技巧（滚动数组）在 DP 中非常实用，可将二维压缩至一维。

✅ 掌握此题，为后续更复杂的路径规划（如带障碍、最小路径和等）打下坚实基础。

github地址: https://github.com/swf2020/LeetCode-Hot100-Solutions