给定一个 m × n 的网格和一个球。球的起始坐标为 (i,j) ，你可以将球移到相邻的单元格内，
或者往上、下、左、右四个方向上移动使球穿过网格边界。但是，你最多可以移动 N 次。
找出可以将球移出边界的路径数量。答案可能非常大，返回 结果 mod 109 7 的值。
示例 1：输入: m = 2, n = 2, N = 2, i = 0, j = 0 输出: 6
解释:
示例 2：输入: m = 1, n = 3, N = 3, i = 0, j = 1 输出: 12
解释:
说明:球一旦出界，就不能再被移动回网格内。
网格的长度和高度在 [1,50] 的范围内。
N 在 [0,50] 的范围内。
解题思路分析1、递归；时间复杂度O(n^3)，空间复杂度O(n^3)
var dp [60][60][60]int
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}
var mod = 1000000007
func findPaths(m int, n int, N int, i int, j int) int {
dp = [60][60][60]int{}
for i := 0; i < 60; i {
for j := 0; j < 60; j {
for k := 0; k < 60; k {
dp[i][j][k] = -1
}
}
}
return dfs(m, n, i 1, j 1, N) // 下标取正
}
func dfs(m, n, i, j, k int) int {
if k < 0 { // 次数够了
return 0
}
if i < 1 || i > m || j < 1 || j > n { // 出界次数 1
return 1
}
if dp[i][j][k] != -1 {
return dp[i][j][k]
}
dp[i][j][k] = 0
for a := 0; a < 4; a { // 上下左右4个方向
x := i dx[a]
y := j dy[a]
dp[i][j][k] = (dp[i][j][k] dfs(m, n, x, y, k-1)) % mod
}
return dp[i][j][k]
}
2、动态规划；时间复杂度O(n^3)，空间复杂度O(n^3)
var dx = []int{-1, 1, 0, 0}
var dy = []int{0, 0, -1, 1}
var mod = 1000000007
func findPaths(m int, n int, N int, i int, j int) int {
dp := [60][60][60]int{}
for k := 1; k <= N; k {
for a := 0; a < m; a {
for b := 0; b < n; b {
for i := 0; i < 4; i {
x := a dx[i]
y := b dy[i]
if x < 0 || x >= m || y < 0 || y >= n { // 出界次数 1
dp[a][b][k]
} else {
dp[a][b][k] = (dp[a][b][k] dp[x][y][k-1]) % mod
}
}
}
}
}
return dp[i][j][N] % mod
}总结
Medium题目，动态规划题目，也可以使用带缓存的递归
