不同路径-LeetCode

62. 不同路径 - Unique Paths

🎯 问题描述（来源于LeetCode）

描述：
一个机器人位于一个 m x n 网格的左上角（起点为 (0,0)）。机器人每次只能向下或向右移动一步。
问机器人到达右下角 (m-1, n-1) 有多少条不同的路径？

说明：

• 1 <= m, n <= 100。
• 题目保证答案在 32 位整数范围内。

示例：

• 示例 1：

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

• 示例 2：

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

💻 解题思路

思路：动态规划（1‑based 数组）

算法步骤

1. 创建 (m+1) x (n+1) 的二维数组 dp，全部初始化为 0。
2. 遍历 i 从 0 到 m-1，j 从 0 到 n-1：
   • 如果 i == 0 and j == 0，则 dp[1][1] = 1（起点）。
   • 否则，dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]。
3. 最后返回 dp[m][n]。

代码实现

from typing import List

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                if i == j == 0:
                    dp[1][1] = 1
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
        return dp[m][n]

📊 性能分析

• 时间复杂度：$O(m \times n)$
• 空间复杂度：$O(m \times n)$，可优化到 $O(n)$（一维数组）

思考

该解法采用 1‑based 索引，避免了初始化第一行和第一列的繁琐。思路清晰，但空间占用较大。对于本题，也可使用组合数学公式直接计算 $C_{m+n-2}^{m-1}$，但动态规划更通用。代码中的 dp[1][1] = 1 是起点，然后利用递推关系计算每个格子的路径数，最终返回 dp[m][n]。注意：由于数组大小多了一圈，实际有效范围是 1..m, 1..n，边界由外层循环保证正确性。