题意ref{:target=”_blank”}
DP,考虑从 边界外 向 边界内 进行状态转移
C++ 代码
class Solution {
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
// 边界case会溢出
if(!maxMove)return 0;
// f[i][j][k] 定义为 从边界走k步到达(i,j)的位置
int f[m][n][maxMove+1];
memset(f, 0x0, sizeof(f));
// 从 边界外 走一步到 边界
for(int i=0; i<m; ++i) {
f[i][0][1]++;
f[i][n-1][1]++;
}
for(int j=0; j<n; ++j) {
f[0][j][1]++;
f[m-1][j][1]++;
}
const int MOD = 1e9+7;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
// 先迭代k的原因是,k需要k-1的信息
for(int k=2; k<=maxMove; ++k) {
for(int i=0; i<m; ++i) {
for(int j=0; j<n; ++j) {
for(int u=0; u<4; ++u) {
int x = i+dx[u], y = j+dy[u];
if(x>=0 && x<m && y>=0 && y<n) {
(f[i][j][k] += f[x][y][k-1]) %= MOD;
}
}
}
}
}
int res = 0;
// 枚举所有的步数方案
for(int k=1; k<=maxMove; ++k) {
// += 返回的是 左值的引用,所以可以这样简写
(res += f[startRow][startColumn][k]) %= MOD;
}
return res;
}
};