576. 出界的路径数

🎯 问题描述（来源于LeetCode）

描述：给定一个 m x n 的网格，一个球最初位于位置 (startRow, startColumn)。球可以移动，每次移动可以向四个方向（上、下、左、右）之一移动一个单元格。如果球移出网格边界，就无法再移动。

给定最大移动次数 maxMove。求出从 (startRow, startColumn) 出发，在不超过 maxMove 次移动内，有多少种路径能让球出界。

说明：

球在出界后即停止。
答案可能很大，请对 $10^9 + 7$ 取模。
$1 <= m, n <= 50$
$0 <= maxMove <= 50$

示例：

示例 1：

1
2
3

输入: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
输出: 6
解释: 有6种路径能让球在2步内出界。

示例 2：

1 2	输入: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1 输出: 12

💻 解题思路

思路1：记忆化搜索 (DFS + Cache)

核心思想：
这是一个典型的带状态限制的递归问题。如果不加优化直接递归，时间复杂度将是指数级的（ $4^{maxMove}$ ），因为每一步都有 4 个方向可选。

我们需要利用记忆化搜索来消除重复计算：

状态定义：dfs(x, y, i) 表示球在坐标 (x, y)，且剩余移动次数为 i 时，出界的路径总数。
重叠子问题：在搜索过程中，同一个位置 (x, y) 在相同的剩余步数 i 下会被多次访问（例如绕路回来）。
备忘录：使用 @cache 装饰器自动记录 (x, y, i) 对应的结果。

算法步骤：

边界判断：如果当前位置 (x, y) 已经不在网格内（即出界），说明找到了一条有效路径，返回 1。
步数耗尽：如果当前位置还在网格内，但剩余步数 i 为 0，则无法出界，返回 0。
状态转移：如果既没出界也没耗尽步数，则向四个方向移动。
- 对每个方向 (dx, dy)，递归计算 dfs(x+dx, y+dy, i-1)。
- 将四个方向的结果累加，并对 $10^9+7$ 取模。

思路1：代码实现

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        mod = 10**9 + 7
        direction = 
        
        @cache
        def dfs(x, y, i):
            # 1. 出界：找到一条路径
            if x < 0 or x >= m or y < 0 or y >= n:
                return 1
            # 2. 没出界但没步数了
            if i == 0:
                return 0
            
            ans = 0
            for dx, dy in direction:
                ans = (ans + dfs(x + dx, y + dy, i - 1)) % mod
            return ans
        
        return dfs(startRow, startColumn, maxMove)

思路1：📊 性能分析

提交结果

运行时间：52ms击败46.46%
内存消耗：27.99MB击败27.27%

复杂度验证

- 解析：主要由 @cache 装饰器存储的状态数量决定，以及递归调用栈的深度（最深为 maxMove）。

思考

为什么用 @cache 而不是自己写字典？
- Python 的 @lru_cache（或简写 @cache）装饰器非常强大，它可以自动将函数的参数作为键（Key），将返回值作为值（Value）存入哈希表。这比手动维护一个三维数组 dp[x][y][i] 要简洁得多，且不易出错。
状态转移的逻辑陷阱：
- 在递归函数中，必须先判断是否出界，再判断是否有步数。因为一旦出界，哪怕没有步数了，也算作一条有效路径。
- 代码中的 ans 累加的是下一层递归的结果，即从邻居节点出发的路径数，这符合“分治”的思想。