576 出界的路径数（动态规划-递推）

左手的ㄟ右手 2022-08-31 11:10 133阅读 0赞

**1. 问题描述：**

给你一个大小为 m x n 的网格和一个球。球的起始坐标为 \[startRow, startColumn\] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你最多可以移动 maxMove 次球。给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 10 ^ 9 + 7 取余后的结果。

**示例 1：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0  
输出：6

**示例 2：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 1][]

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

**提示：**

1 <= m, n <= 50  
0 <= maxMove <= 50  
0 <= startRow < m  
0 <= startColumn < n  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/out-of-boundary-paths

**2. 思路分析：**

分析题目可以知道我们需要求解出从当前 \[startRow, startColumn\]位置出发所有能够到达边界的方案数目，因为能够到达目标位置的方案数目可能是很多的，所以我们考虑使用动态规划中**递推**思路解决（类似于之前力扣中机器人走路径的题目）。我们可以从边界往目标位置走感觉会更好处理一点（下图为初始化的dp数组的边界），所以下面采用从边界往目标位置走的方法。分析题目可以知道我们需要知道当前二维平面的位置，并且需要记录一下到达某个位置所需要的步数，所以我们可以定义三维数组，其中dp\[x\]\[y\]\[k\]可以定义为从边界到达位置(x，y)移动了k步，对于当前的状态dp\[x\]\[y\]\[k\]，我们可以从上下左右四个方向走到当前的位置(x，y)所以对于当前的dp\[x\]\[y\]\[k\]总共有四个状态的转移。所以我们可以使用四层循环进行状态的计算，第一层循环表示移动的步数（每一次可以尝试从某一个位置走一步走到下一个位置），第二个循环表示当前的横坐标，第三层循环表示当前的纵坐标，第四层循环表示上下左右方向对应的状态转移，因为求解的是方案数目所以对于当前的状态我们累加上上一个可能的状态的方案数目即可。最后我们还需要枚举一下答案，因为到达目标位置可能需要的步数为1~maxMove。这道题目也是一道非常经典的递推题目。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 2][]

**3. 代码如下：**

class Solution:
        # m表示行, n表示列
        def findPaths(self, m: int, n: int, maxMove: int, x: int, y: int) -> int:
            if maxMove == 0: return 0
            dp = [[[0] * (maxMove + 1) for i in range(n + 2)] for j in range(m + 2)]
            mod = 10 ** 9 + 7
            # 初始化边界, 二维矩阵对应的最上,下,左,右对应的两个方案
            for i in range(n):
                # 第一行与最后一行
                dp[0][i][1] += 1
                dp[m - 1][i][1] += 1
            for i in range(m):
                # 第一列与最后一列
                dp[i][0][1] += 1
                dp[i][n - 1][1] += 1
    
            pos = [[0, 1], [0, -1], [-1, 0], [1, 0]]
            for k in range(1, maxMove + 1):
                for i in range(m):
                    for j in range(n):
                        for u in range(4):
                            x0, y0 = i + pos[u][0], j + pos[u][1]
                            if 0 <= x0 < m and 0 <= y0 < n:
                                dp[i][j][k] = (dp[i][j][k] + dp[x0][y0][k - 1]) % mod
            # 枚举答案,k可以从1~maxMove 说明从没某个位置到达目标位置可以走的步数
            res = 0
            for k in range(1, maxMove + 1):
                res = (res + dp[x][y][k]) % mod
            return res

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/927c3a483713450cb5e40d74570a1b30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 1]: /images/20220829/5c568952482943369dd6b2655f7485a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 2]: /images/20220829/a28af9f522f24a54bcd6efe034eef5a0.png