62. 不同路径

题目链接：62. 不同路径

题目描述

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

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

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

核心思考：动态规划（自顶向下 + 记忆化）

本题是典型的路径计数类动态规划问题。由于机器人只能向下或向右走，意味着要到达位置 (i, j)，它只能是从上方 (i-1, j) 或者左方 (i, j-1) 走过来的。

1. 状态定义：设 dfs(i, j) 为到达坐标 (i, j) 的唯一路径总数。
2. 转移方程：dfs(i, j) = dfs(i - 1, j) + dfs(i, j - 1)。
3. 递归边界：
   • 如果 i < 0 或 j < 0：超出了网格范围，路经数为 0。
   • 如果 i == 0 或 j == 0：说明此时机器人正处于第一行或第一列。由于只能向右/向下走，此时到达这些边缘位置只有唯一的一条直线路径，返回 1。
4. 性能保障：
   使用 Python 的 @cache 装饰器。这实质上是实现了一个记忆化搜索。它会将计算过的 (i, j) 对应的路径数缓存起来，避免了指数级的重复子问题计算，将时间复杂度降低到 $O(m \times n)$。

虽然此题也可以通过单纯的组合数学公式 $C_{m+n-2}^{m-1}$ 解决，但动态规划的思路在处理带有“障碍物”等复杂变体时更具普适性。

解题思路 (Python)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @cache
        def dfs(i, j):
            # 边界检查：出界
            if i < 0 or j < 0:
                return 0
            # 起点所在的行或列，路径数均为 1
            if i == 0 or j == 0:
                return 1
            
            # 当前格子的路径数 = 上方格子路径数 + 左方格子路径数
            return dfs(i - 1, j) + dfs(i, j - 1)

        # 从终点 (m-1, n-1) 开始自顶向下递归
        return dfs(m - 1, n - 1) 

复杂度分析

• 时间复杂度：$O(M \times N)$，其中 $M$ 和 $N$ 分别为网格的长和宽。每个格子节点 (i, j) 只会被计算并缓存一次。
• 空间复杂度：$O(M \times N)$。由递归调用产生的最大栈空间以及缓存字典的存储空间开销共同决定。