Out of Boundary Paths (Leetcode 576)

一般矩阵题加了一个step的限制条件，则考虑用三维dp来做了。而递推公式如下(四个方向，step-1结果的和)

dp[i][j][step] = dp[i-1][j][step-1] + dp[i+1][j][step-1] + dp[i][j-1][step-1] + dp[i][j+1][step-1]

第一种解法：
https://discuss.leetcode.com/topic/88539/easy-understanding-c-python-solution-with-explanation

思路直接，用dfs, 用中心向外正向搜索。如果对应的坐标＋步数没被访问过，则以此继续向外dfs.

class Solution {
public:

    int find_util(int i, int j, int step, vector<vector<vector<int>>> &dp){
        if(i < 0 || i >= row || j < 0 || j >= col) return 1;
        else if(step == 0) return 0;
        int ans = 0;
        if(dp[i][j][step-1] == -1){
            for(auto it : directions){
                int x = i + it.first, y = j + it.second;
                ans = (ans + find_util(x, y, step-1, dp) % mod) % mod;
            }
            dp[i][j][step-1] = ans;
        }
        return dp[i][j][step-1];
    }

    int findPaths(int m, int n, int N, int i, int j) {
        if(N <= 0) return 0;
        row = m; col = n;
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(N, -1)));
        return find_util(i, j, N, dp);
    }
private:
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    const int mod = 1e9 + 7;
    int row, col;
};

第二种方法是反向，由step1推到stepn, 由外向内收缩。在一步时，仅仅最外围的坐标可以获得值，而里层点都是０，因为里层点一步走不出去。二步，三步以此类推，均可由一步逆推出来。这种方法还可以用滚动数组节省空间。而值得注意的是一定要用uint或long，来防止overflow.

https://discuss.leetcode.com/topic/88492/c-6-lines-dp-o-n-m-n-6-ms

int findPaths(int m, int n, int N, int i, int j) {
        if(N <= 0) return 0;
        const int mod = 1e9 + 7;
        vector<vector<vector<long>>> dp(m, vector<vector<long>>(n, vector<long>(N+1, 0)));
        
        for(int step = 1; step <= N; step++){
            for(int row=0; row<m; row++){
                for(int col=0; col<n; col++){
                   dp[row][col][step] = ((row == 0 ? 1 : dp[row-1][col][step-1]) + (row == m-1 ? 1 : dp[row+1][col][step-1]) + (col == 0 ? 1 : dp[row][col-1][step-1]) + (col == n-1 ? 1 : dp[row][col+1][step-1])) % mod;
                }
            }
        }
        return dp[i][j][N];
        
    }