[打卡]8.15_576. 出界的路径数
相关题解:DFS & 剪枝 & 记忆化搜索 & DP & 降维优化,层层递进)
AC代码:
typedef long long LL;
LL dp[55][55][55];
int _m, _n, _maxMov;
class Solution {
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
_m = m;
_n = n;
_maxMov = maxMove;//将它赋值给全局变量
memset(dp, -1, sizeof dp);//将dp数组全赋为-1,表示全没访问过
return dfs(startRow, startColumn, 0);//搜索
}
inline long dfs(int i, int j, int s) {
if (s > _maxMov) return 0;//如果当前步数大于规定步数,则不行
if (i < 0 || j < 0 || i >= _m || j >= _n) return 1;//如果越界则满足条件,返回1
if (dp[i][j][s] != -1) return dp[i][j][s];//dp[i][j][s]代表 当前坐标(i,j) 步数为 s 的能越界的路径数量
//上下左右四个方向去找
dp[i][j][s] += (dfs(i + 1, j, s + 1) + dfs(i - 1, j, s + 1) + dfs(i, j + 1, s + 1) + dfs(i, j - 1, s + 1));
return dp[i][j][s];
}
};
记忆化搜索yyds,这题其实考的是dp,但三维dp我不懂