出界的路径数
程序员文章站
2022-07-15 11:37:23
...
一、题目描述
题目链接:https://leetcode-cn.com/problems/out-of-boundary-paths/
二、题目分析
经典记忆搜索,题解参考:https://leetcode-cn.com/problems/out-of-boundary-paths/solution/ji-yi-hua-di-gui-chao-jian-ji-by-pwrliang/
三、代码
private int[] dirs = {0,1,0,-1,0};
public int findPaths(int m, int n, int N, int i, int j) {
Integer[][][] memo = new Integer[m][n][N+1];
return dfs(m,n,memo,N,i,j);
}
private int dfs(int m, int n, Integer[][][] memo, int N, int i, int j) {
if (N < 0) return 0;
if (i < 0 || i == m || j < 0 || j == n) return 1;
if (memo[i][j][N] != null) return memo[i][j][N];
int sum = 0;
for (int k = 0; k < 4; ++k) {
sum = (int) (((long)sum + dfs(m,n,memo,N-1,i+dirs[k],j+dirs[k+1])) % 1000000007);
}
memo[i][j][N] = sum;
return sum;
}