标签: 动态规划
难度: Medium
给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。
给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。
示例 1：
输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0 输出：6
示例 2：
输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1 输出：12
提示：
1 <= m, n <= 500 <= maxMove <= 500 <= startRow < m0 <= startColumn < n运行时间: 65 ms
内存: 21.4 MB
class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
MOD = 10 ** 9 + 7
if maxMove == 0:
return 0
@cache
def countPaths(currX: int, currY: int, maxMove: int) -> int:
if maxMove == 1:
return (currX == 0) + (currX == m - 1) + (currY == 0) + (currY == n - 1)
return sum([
countPaths(currX - 1, currY, maxMove - 1) if currX > 0 else 1,
countPaths(currX + 1, currY, maxMove - 1) if currX < m - 1 else 1,
countPaths(currX, currY - 1, maxMove - 1) if currY > 0 else 1,
countPaths(currX, currY + 1, maxMove - 1) if currY < n - 1 else 1
]) % MOD
return countPaths(startRow, startColumn, maxMove)
这个题解使用了记忆化递归的方法。首先判断如果最大移动次数为0，直接返回0。然后定义了一个递归函数countPaths，用来计算从当前位置(currX, currY)出发，在剩余的maxMove步内出界的路径数量。如果只剩下1步，那么只需判断当前位置是否在边界上，在的话就返回1，否则返回0。如果还有多步，就分别向上下左右四个方向递归调用countPaths，如果某个方向已经出界，则该方向的返回值为1。最后将四个方向的结果求和取模即可。主函数中调用countPaths(startRow, startColumn, maxMove)得到最终结果。
时间复杂度: O(m * n * maxMove)
空间复杂度: O(m * n * maxMove)
class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
MOD = 10 ** 9 + 7
if maxMove == 0:
return 0
@cache
def countPaths(currX: int, currY: int, maxMove: int) -> int:
# 如果只剩下1步，判断当前位置是否在边界上
if maxMove == 1:
return (currX == 0) + (currX == m - 1) + (currY == 0) + (currY == n - 1)
# 否则向四个方向递归调用，并将结果求和
return sum([
countPaths(currX - 1, currY, maxMove - 1) if currX > 0 else 1, # 向上移动
countPaths(currX + 1, currY, maxMove - 1) if currX < m - 1 else 1, # 向下移动
countPaths(currX, currY - 1, maxMove - 1) if currY > 0 else 1, # 向左移动
countPaths(currX, currY + 1, maxMove - 1) if currY < n - 1 else 1 # 向右移动
]) % MOD
return countPaths(startRow, startColumn, maxMove)
在递归函数`countPaths`中，当只剩下1步时，通过检查当前位置是否在边界上来确定是否返回1，确实确保了所有可能的出界路径被正确计算。这里的逻辑基于的是，如果还有一步可以走，且当前位置已经在边界上（顶部、底部、左侧或右侧），那么在下一步必然可以直接走出界，因此直接返回1代表这一可能性。如果不在边界上，则无法在一步内走出界，因此返回0。这样的处理方式精确地覆盖了所有能在最后一步直接走出界的情况。
这种处理方式不会导致路径的重复计数。在题解中，每个递归调用都是基于当前位置和剩余可移动的步数来决定的。如果某个方向已经出界，即当前方向的下一步没有有效的格子可走，直接返回1是因为这确实代表了一条成功的出界路径。由于每次递归调用都是独立考虑各个方向的，所以即使在边界附近，每个方向的出界都是独立计算，不会重复。
在没有任何移动时直接返回0是合理的，因为题目要求的是在给定的移动次数内出边界的路径数量。即使开始位置已经在边界上，如果没有移动次数（maxMove为0），则没有任何移动可以执行，因此不能形成任何有效的出界路径。这种设定是基于题目要求的移动次数内完成出界的规则。
使用`@cache`装饰器可以有效地避免在递归过程中对相同参数值的重复计算，从而显著提高性能。在这个问题中，递归函数`countPaths`有三个参数：当前坐标（currX, currY）和剩余可移动步数（maxMove）。由于在递归过程中可能会多次访问到相同的位置与相同的剩余步数，使用缓存可以保存这些结果，避免重复的计算过程。每次调用时，如果这些参数的组合之前已经计算过，就直接从缓存中返回结果，减少了计算量和执行时间。