576. 出界的路径数

DFS

class Solution {
     int MOD = (int)1e9+7;
    int[][][] cache;
    int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int dfs(int m, int n, int move, int x, int y){
        //base case 1:出界了
        if(x < 0 || x >= m || y < 0 || y >= n){
            return 1;
        }
        //base case 2:次数用完了，没出界，证明不是合法路径
        if(move == 0){
            return 0;
        }
        if(cache[x][y][move] != -1){
            return cache[x][y][move];
        }
        cache[x][y][move] = 0;
        for(int i = 0; i < 4; i++){
            int newX = x + dirs[i][0];
            int newY = y + dirs[i][1];
            cache[x][y][move] += dfs(m, n, move - 1, newX, newY);
            cache[x][y][move] %= MOD;
        }
        return cache[x][y][move];
    }
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        cache = new int[m][n][maxMove + 1];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                Arrays.fill(cache[i][j], -1);
            }
        }
        return dfs(m, n, maxMove, startRow, startColumn);
    }
}

DP

class Solution {
    int mod = (int)1e9+7;
    int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    //获取边界点(x, y)对应的出界路径数
    int getBaseCase(int m, int n, int x, int y){
        int sum = 0;
        sum += (x == 0 ? 1 : 0);
        sum += (x == m - 1 ? 1 : 0);
        sum += (y == 0 ? 1 : 0);
        sum += (y == n - 1 ? 1 : 0);
        return sum;
    }
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        //状态定义
        //dp[i][j][k]代表处于(i, j)且当前移动次数为k的出界路径数
        int[][][] dp = new int[m][n][maxMove + 1];
        //状态初始化
        //预处理所有边界格子的出界路径数
        for(int i = 0; i < n; i++){//处理第一行和最后一行
            //第一行的第i列
            int case1 = getBaseCase(m, n, 0, i);
            //第m行的第i列
            int case2 = getBaseCase(m, n, m - 1, i);
            //对所有移动次数>=1的情况，处于边界点都+1
            for(int k = 1; k <= maxMove; k++){
                dp[0][i][k] = case1;
                dp[m - 1][i][k] = case2;
            }
        }
        for(int i = 0; i < m; i++){//处理第一列和最后一列
            //第1列的第i行
            int case1 = getBaseCase(m, n, i, 0);
            //第n列的第i行
            int case2 = getBaseCase(m, n, i, n - 1);
            for(int k = 1; k <= maxMove; k++){
                dp[i][0][k] = case1;
                dp[i][n - 1][k] = case2;
            }
        }
        //状态转移
        //dp[i][j][k] = dp[i-1][j][k-1] + dp[i][j-1][k-1] + dp[i+1][j][k-1] + dp[i][j+1][k-1]
        //最外循环枚举移动次数k
        for(int k = 1; k <= maxMove; k++){
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    //尝试上、下左、右四个方向
                    for(int it = 0; it < 4; it++){
                        int x = i + dirs[it][0];
                        int y = j + dirs[it][1];
                        if(x >= 0 && x < m && y >= 0 && y < n){
                            dp[i][j][k] += dp[x][y][k -1];
                            dp[i][j][k] %= mod;
                        }
                    }
                }
            }
        }
        return dp[startRow][startColumn][maxMove];
    }
}

收获：尝试从记忆化搜索转化为DP，并且考虑如何从base case找到对应的dp数组初始化。