576. 出界的路径数
给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。
给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。
示例 1：
输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
输出：6
提示：
- 1 <= m, n <= 50
- 0 <= maxMove <= 50
- 0 <= startRow < m
- 0 <= startColumn < n
方法一: dfs
不用标记位置.
相同的出口位置,不同的步数也算不同的方案
class Solution {
public:
const int MOD = 1e9 + 7;
int dir[4][2]={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int ans= 0;
int u[55][55];
int mm, nn;
void dfs(int i, int j, int step, int maxMove) {
if(step >= maxMove) return;
for(int k = 0; k < 4; k++) {
int x = i + dir[k][0], y = j + dir[k][1];
if(x < 0 || x >= mm || y < 0 || y >= nn) {
ans++;
ans %= MOD;
continue ;
}else {
dfs(x, y, step + 1, maxMove);
}
}
}
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
mm = m, nn =n;
dfs(startRow, startColumn, 0, maxMove);
return ans;
}
};
- 最后还是超时了,
方法二:记忆化搜索 | 动态规划
上面分析到,相同的位置可能有多种方案,当方案走到i,j,k(位置+步数)时可以记录下来,下次遍历到直接加起来就可以
记忆化搜索联系最紧的就是动态规划,把步数再加一个状态->dp[i][j][k],就表示i,j位置,用了k步的方案数
class Solution {
public:
int dp[55][55][55];
const int MOD = 1e9 + 7;
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
//初始化的时候四周有一种方案,角有两种,需要预处理
for(int k = 1; k <= maxMove; k++) {
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0) dp[i][j][k]++;
if(j == 0) dp[i][j][k]++;
if(i == m -1) dp[i][j][k]++;
if(j == n -1) dp[i][j][k]++;
for(auto h : dir) {
int x = i + h[0], y = j + h[1];
if(!(x < 0 || x >= m || y < 0 || y >= n)){
dp[i][j][k] = (dp[i][j][k] + dp[x][y][k - 1]) % MOD;
}
}
}
}
}
return dp[startRow][startColumn][maxMove];
}
};