题目描述
这是 LeetCode 上的 576. 出界的路径数 ，难度为 中等。
Tag : 「路径 DP」、「动态规划」、「记忆化搜索」
给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。
你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。
你最多可以移动 maxMove 次球。
给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。
因为答案可能非常大，返回对 10^9 + 7109+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 <= 50
- 0 <= maxMove <= 50
- 0 <= startRow < m
- 0 <= startColumn < n
基本分析
通常来说，朴素的路径 DP 问题之所以能够使用常规 DP 方式进行求解，是因为只能往某一个方向（一维棋盘的路径问题）或者只能往某两个方向（二维棋盘的路径问题）移动。
这样的移动规则意味着，我们不会重复进入同一个格子。
从图论的意义出发：将每个格子视为点的话，如果能够根据移动规则从 a 位置一步到达 b 位置，则说明存在一条由 a 指向 b 的有向边。
也就是说，在朴素的路径 DP 问题中，“单向”的移动规则注定了我们的图不存在环，是一个存在拓扑序的有向无环图，因此我们能够使用常规 DP 手段来求解。
回到本题，移动规则是四联通，并不是“单向”的，在某条出界的路径中，我们是有可能重复进入某个格子，即存在环。
因此我们需要换一种 DP 思路进行求解。
记忆化搜索
通常在直接 DP 不好入手的情况下，我们可以先尝试写一个「记忆化搜索」的版本。
那么如果是让你设计一个 DFS 函数来解决本题，你会如何设计？
我大概会这样设计：
int dfs(int x, int y, int k) {} 复制代码
重点放在几个「可变参数」与「返回值」上：(x,y)(x,y) 代表当前所在的位置，kk 代表最多使用多少步，返回值代表路径数量。
根据 DP-动态规划 第八讲 的学习中，我们可以确定递归出口为：
- 当前到达了棋盘外的位置，说明找到了一条出界路径，返回 11；
- 在条件 11 不满足的前提下，当剩余步数为 00（不能再走下一步），说明没有找到一条合法的出界路径，返回 00。
主逻辑则是根据四联通规则进行移动即可，最终答案为 dfs(startRow, startColumn, maxMove)。
代码：
class Solution { int MOD = (int)1e9+7; int m, n, max; int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}}; int[][][] cache; public int findPaths(int _m, int _n, int _max, int r, int c) { m = _m; n = _n; max = _max; cache = new int[m][n][max + 1]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k <= max; k++) { cache[i][j][k] = -1; } } } return dfs(r, c, max); } int dfs(int x, int y, int k) { if (x < 0 || x >= m || y < 0 || y >= n) return 1; if (k == 0) return 0; if (cache[x][y][k] != -1) return cache[x][y][k]; int ans = 0; for (int[] d : dirs) { int nx = x + d[0], ny = y + d[1]; ans += dfs(nx, ny, k - 1); ans %= MOD; } cache[x][y][k] = ans; return ans; } } 复制代码
动态规划
根据我们的「记忆化搜索」，我们可以设计一个二维数组 f[][]f[][] 作为我们的 dp 数组：
- 第一维代表 DFS 可变参数中的 (x,y)(x,y) 所对应 indexindex。取值范围为 [0, m*n)[0,m∗n)
- 第二维代表 DFS 可变参数中的 kk。取值范围为 [0,max][0,max]
dp 数组中存储的就是我们 DFS 的返回值：路径数量。
根据 dp 数组中的维度设计和存储目标值，我们可以得知「状态定义」为：
f[i][j]f[i][j] 代表从位置 ii 出发，可用步数不超过 jj 时的路径数量。
至此，我们只是根据「记忆化搜索」中的 DFS 函数的签名，就已经得出我们的「状态定义」了，接下来需要考虑「转移方程」。
当有了「状态定义」之后，我们需要从「最后一步」来推导出「转移方程」：
由于题目允许往四个方向进行移动，因此我们的最后一步也要统计四个相邻的方向。
由此可得我们的状态转移方程：
f[(x,y)][step] = f[(x-1,y)][step-1]+f[(x+1,y)][step-1]+f[(x,y-1)][step-1]+f[(x,y+1)][step-1]f[(x,y)][step]=f[(x−1,y)][step−1]+f[(x+1,y)][step−1]+f[(x,y−1)][step−1]+f[(x,y+1)][step−1]
注意，转移方程中 dp 数组的第一维存储的是 (x,y)(x,y) 对应的 idxidx。
从转移方程中我们发现，更新 f[i][j]f[i][j] 依赖于 f[x][j-1]f[x][j−1]，因此我们转移过程中需要将最大移动步数进行「从小到大」枚举。
至此，我们已经完成求解「路径规划」问题的两大步骤：「状态定义」&「转移方程」。
但这还不是所有，我们还需要一些 有效值 来滚动下去。
其实就是需要一些「有效值」作为初始化状态。
观察我们的「转移方程」可以发现，整个转移过程是一个累加过程，如果没有一些有效的状态（非零值）进行初始化的话，整个递推过程并没有意义。
那么哪些值可以作为成为初始化状态呢？
显然，当我们已经位于矩阵边缘的时候，我们可以一步跨出矩阵，这算作一条路径。
同时，由于我们能够往四个方向进行移动，因此不同的边缘格子会有不同数量的路径。
换句话说，我们需要先对边缘格子进行初始化操作，预处理每个边缘格子直接走出矩阵的路径数量。
目的是为了我们整个 DP 过程可以有效的递推下去。
可以发现，动态规划的实现，本质是将问题进行反向：原问题是让我们求从棋盘的特定位置出发，出界的路径数量。实现时，我们则是从边缘在状态出发，逐步推导回起点的出界路径数量为多少。
代码：
class Solution { int MOD = (int)1e9+7; int m, n, max; int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}}; public int findPaths(int _m, int _n, int _max, int r, int c) { m = _m; n = _n; max = _max; int[][] f = new int[m * n][max + 1]; // 初始化边缘格子的路径数量 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0) add(i, j, f); if (j == 0) add(i, j, f); if (i == m - 1) add(i, j, f); if (j == n - 1) add(i, j, f); } } // 从小到大枚举「可移动步数」 for (int k = 1; k <= max; k++) { // 枚举所有的「位置」 for (int idx = 0; idx < m * n; idx++) { int[] info = parseIdx(idx); int x = info[0], y = info[1]; for (int[] d : dirs) { int nx = x + d[0], ny = y + d[1]; if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; int nidx = getIdx(nx, ny); f[idx][k] += f[nidx][k - 1]; f[idx][k] %= MOD; } } } return f[getIdx(r, c)][max]; } void add(int x, int y, int[][] f) { for (int k = 1; k <= max; k++) { f[getIdx(x, y)][k]++; } } int getIdx(int x, int y) { return x * n + y; } int[] parseIdx(int idx) { return new int[]{idx / n, idx % n}; } } 复制代码
- 时间复杂度：共有 m * n * maxm∗n∗max 个状态需要转移，复杂度为 O(m * n * max)O(m∗n∗max)
- 空间复杂度：O(m * n * max)O(m∗n∗max)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.576 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
