推 JIWP: 大師 01/26 15:49
推 sustainer123: 一直dp一直爽 哇哇嗚嗚嗚 01/26 15:50
→ JerryChungYC: 不會dp 放棄 01/26 18:28
576. Out of Boundary Paths
給你一些數字 m = 列數, n = 行數, maxMove = 移動步數, startRow 和 startColumn為
矩陣的出發座標，求出移動 1~maxMove 步後共有幾種結果會走出矩陣外外，因為數字很大
要取MOD。
1.模擬從起始座標往四個方向前進，如果出界就把res+1 否則繼續往四個方向不斷dfs，
直到沒步數或出界。
2.直接跑會TLE，因為在走的過程中可能會走到已經算過的點，所以可以用memo記憶化搜
索，dp[i][j][k] 表示當前位置最多使用 k 步會走出去的路徑數量。
Java Code:
--------------------------------------------
class Solution {
private int m, n;
private Integer[][][] cache;
private int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int findPaths(int m, int n, int maxMove, int startRow, int
startColumn) {
this.m = m;
this.n = n;
cache = new Integer[m][n][maxMove + 1];
return dfs(startRow, startColumn, maxMove);
}
private int dfs(int y, int x, int step) {
if (y < 0 || x < 0 || y == m || x == n) {
return 1;
}
if (step == 0) {
return 0;
}
if (cache[y][x][step] != null) {
return cache[y][x][step];
}
int ans = 0;
for (int[] dir : dirs) {
ans += dfs(y + dir[0], x + dir[1], step - 1);
ans %= 1e9+7;
}
return cache[y][x][step] = ans;
}
}
--------------------------------------------
--
https://i.imgur.com/PIoxddO.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706255318.A.37D.html