[打卡]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我不懂

本文链接：