四种解法，每种方法分别用C++和Python实现。共8个version代码。从简单的递归，到记忆化优化，再到两种dp代码实现。注释很详细，有疑问欢迎留言。
// Brute force recursion: TLE
class Solution1 {
public:
int findPaths(int m, int n, int N, int i, int j) {
return dfs(m, n, N, i, j);
}
int dfs(int m, int n, int N, int i, int j) {
if (i < 0 || j < 0 || i >= m || j >= n) {
return 1;
}
if (N == 0) {
return 0; // after N step still within range
}
int res = 0;
for (const auto& dir : dirs) {
auto ni = i + dir[0];
auto nj = j + dir[1];
res += dfs(m, n, N - 1 , ni, nj);
}
return res;
}
private:
vector<vector<int>> dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
};
// Memoization: AC
class Solution2 {
public:
int findPaths(int m, int n, int N, int i, int j) {
memo = vector<vector<vector<int>>> (m, vector<vector<int>>(n, vector<int>(N + 1, -1)));
return dfs(m, n, N, i, j);
}
long dfs(int m, int n, int N, int i, int j) {
if (i < 0 || j < 0 || i >= m || j >= n) {
return 1;
}
if (memo[i][j][N] != -1) {
return memo[i][j][N];
}
if (N == 0) {
return 0; // after N step still within range
}
long res = 0;
for (const auto& dir : dirs) {
auto ni = i + dir[0];
auto nj = j + dir[1];
res += dfs(m, n, N - 1 , ni, nj);
res %= MOD;
}
memo[i][j][N] = res;
return memo[i][j][N];
}
private:
vector<vector<int>> dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
vector<vector<vector<int>>> memo;
const int MOD = 1000000007;
};
// DP1: AC
class Solution3 {
public:
int findPaths(int m, int n, int N, int i, int j) {
vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(N + 1, 0)));
long res = 0;
dp[i][j][0] = 1; // start
for (int k = 1; k <= N; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (const auto& dir : dirs) {
auto ni = i + dir[0];
auto nj = j + dir[1];
if (ni < 0 || nj < 0 || ni >= m || nj >= n) {
// out of board, accmulate the result
res = (res + dp[i][j][k - 1]) % MOD;
} else {
// within board, the total ways of arriving at pos (ni, nj)
// in k steps equals the total ways of arriving at pos (i, j)
// in (k - 1) step and then arriving at (ni, nj) from 4 dirs
dp[ni][nj][k] = (dp[ni][nj][k] + dp[i][j][k - 1]) % MOD;
}
res %= MOD;
}
}
}
}
return res;
}
private:
vector<vector<int>> dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
const int MOD = 1000000007;
};
// DP2: AC (think reverse, the problem is equivalent to starting from outside, in k steps
// how many ways to arrive at postion (r, c))
class Solution {
public:
int findPaths(int m, int n, int K, int r, int c) {
vector<vector<vector<long>>> dp(K + 1, vector<vector<long>>(m, vector<long>(n, 0)));
long res = 0;
for (int k = 1; k <= K; k++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
long up = (i == 0 ? 1 : dp[k - 1][i - 1][j]);
long down = (i == m - 1 ? 1 : dp[k - 1][i + 1][j]);
long left = (j == 0 ? 1 : dp[k - 1][i][j - 1]);
long right = (j == n - 1 ? 1 : dp[k - 1][i][j + 1]);
dp[k][i][j] = (up + down + left + right) % MOD;
}
}
}
return dp[K][r][c];
}
private:
const int MOD = 1000000007;
};
#Brute force recursion: TLE
class Solution1(object):
def findPaths(self, m, n, N, i, j):
def dfs(m, n, N, i, j):
if (i < 0 or j < 0 or i >= m or j >= n):
return 1
if (N == 0):
return 0 # after N step still within range
res = 0
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
for dir in dirs:
ni = i + dir[0]
nj = j + dir[1]
res += dfs(m, n, N - 1 , ni, nj);
return res;
return dfs(m, n, N, i, j)
#Memoization: AC
class Solution2(object):
def findPaths(self, m, n, N, i, j):
MOD = 1000000007;
memo = [[[-1] * (N + 1) for _ in range(n + 1)] for _ in range(m + 1)]
def dfs(m, n, N, i, j):
if (i < 0 or j < 0 or i >= m or j >= n):
return 1
if (N == 0):
return 0 # after N step still within range
if (memo[i][j][N] != -1):
return memo[i][j][N]
res = 0
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
for dir in dirs:
ni = i + dir[0]
nj = j + dir[1]
res += dfs(m, n, N - 1 , ni, nj);
memo[i][j][N] = res % MOD;
return memo[i][j][N];
return dfs(m, n, N, i, j)
# DP1: AC
class Solution3(object):
def findPaths(self, m, n, N, i, j):
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
MOD = 1000000007;
dp = [[[0] * (N + 1) for _ in range(n + 1)] for _ in range(m + 1)]
res = 0
dp[i][j][0] = 1 # start
for k in range(1, N + 1):
for i in range(0, m):
for j in range(0, n):
for dir in dirs:
ni = i + dir[0]
nj = j + dir[1]
if (ni < 0 or nj < 0 or ni >= m or nj >= n):
# out of board, accmulate the result
res = (res + dp[i][j][k - 1]) % MOD
else:
# within board, the total ways of arriving at pos (ni, nj)
# in k steps equals the total ways of arriving at pos (i, j)
# in (k - 1) step and then arriving at (ni, nj) from 4 dirs
dp[ni][nj][k] = (dp[ni][nj][k] + dp[i][j][k - 1]) % MOD
res %= MOD;
return res;
# DP2: AC (think reverse, the problem is equivalent to starting from outside, in k steps
# how many ways to arrive at postion (r, c))
class Solution(object):
def findPaths(self, m, n, K, r, c):
MOD = 1000000007;
dp = [[[0] * (n) for _ in range(m + 1)] for _ in range(K + 2)]
res = 0;
for k in range(1, K + 1):
for i in range(0, m):
for j in range(0, n):
up = (1 if i == 0 else dp[k - 1][i - 1][j])
down = (1 if i == m - 1 else dp[k - 1][i + 1][j])
left = (1 if j == 0 else dp[k - 1][i][j - 1])
right = (1 if j == n - 1 else dp[k - 1][i][j + 1])
dp[k][i][j] = (up + down + left + right) % MOD
return dp[K][r][c];