// DFS 记忆化搜索
// 时间空间 O(m*n*maxMove)
const findPaths = (m: number, n: number, maxMove: number, startRow: number, startColumn: number): number => {
const MOD: number = 1e9 + 7;
const memo: Map<string, number> = new Map<string, number>();
// i: startX, j: startY, k: maxMove, ret: path num to move out of border
const dfs = (i: number, j: number, k: number): number => {
if (k < 0) return 0;
if (i < 0 || j < 0 || i > m - 1 || j > n - 1) return 1;
const key: string = `${i}-${j}-${k}`;
if (memo.has(key)) return memo.get(key);
let res: number = 0;
const [directX, directY] = [[0, 0, 1, -1], [1, -1, 0, 0]];
for (const idx in directX) {
res += dfs(i + directX[idx], j + directY[idx], k - 1);
}
res %= MOD;
memo.set(key, res);
return res;
};
return dfs(startRow, startColumn, maxMove);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22