题目地址：

https://www.lintcode.com/problem/out-of-boundary-paths/description

给定一个$m\times n$的网格和一个球，球的起始坐标是$(i,j)$，每一步可以将球向四个方向移动一格，最多允许移动$N$次，问移动出界的路径总数是多少。最后答案模$10^9+7$之后再返回。规定一旦球出界了，就不能再移动了。

动态规划方法参考https://blog.csdn.net/qq_46105170/article/details/109689458。记忆化搜索方法如下：

设$f[i][j][s]$是已经走过$s$步走到$(i,j)$这个位置的情况下，走出界的路径总数。那么$f[i][j][s]$可以按照下一步走到哪儿来分类，则有：$$\begin{gathered} f[i][j][s]=f[i-1][j][s+1]+f[i+1][j][s+1] \\ +f[i][j-1][s+1]+f[i][j+1][s+1] \end{gathered}$$边界条件，如果中途首次走到了界外，那$f[i][j][s]=1$，否则的话，如果仍然在界内，并且$s=N$，那么$f$取$0$。答案就是$f[i][j][0]$。代码如下：

import java.util.Arrays; public class Solution { private int MOD = (int) (1E9 + 7); /** * @param m: an integer * @param n: an integer * @param N: an integer * @param i: an integer * @param j: an integer * @return: the number of paths to move the ball out of grid boundary */ public int findPaths(int m, int n, int N, int i, int j) { // Write your code here long[][][] dp = new long[m][n][N]; for (int k = 0; k < dp.length; k++) { for (int l = 0; l < dp[0].length; l++) { Arrays.fill(dp[k][l], -1); } } return (int) (dfs(i, j, m, n, 0, N, dp) % MOD); } // 返回已经走了step步，从(x, y)出发，接下来走出界的路径总数 private long dfs(int x, int y, int m, int n, int step, int N, long[][][] dp) { // 如果走出界了，那接下来就不能动了，路径数就是1 if (outBound(x, y, m, n)) { return 1; } // 否则说明当前在界内，如果已经走了N步了，还没出界，则接下来不能继续走了，路径数是0 if (step == N) { return 0; } // 有记忆，则调取记忆 if (dp[x][y][step] != -1) { return dp[x][y][step]; } long res = 0; // 枚举四个方向 int[] d = {1, 0, -1, 0, 1}; for (int i = 0; i < 4; i++) { int nextX = x + d[i], nextY = y + d[i + 1]; res += dfs(nextX, nextY, m, n, step + 1, N, dp) % MOD; } // 存一下记忆 dp[x][y][step] = res; return res; } private boolean outBound(int x, int y, int m, int n) { return !(0 <= x && x < m && 0 <= y && y < n); } }

时空复杂度$O(Nmn)$。

注解：记忆化搜索的时候，一般会把记忆数组先赋值为一个不可能取到的值，这样一旦数组更新了，就能很好的发现，从而调取记忆。