leetcode 576. Out of Boundary Paths | 576. 出界的路径数（暴力递归-＞傻缓存-＞dp）

https://leetcode.com/problems/out-of-boundary-paths/

经典的 从递归到 dp，不多说，上代码。

class Solution {
    public static final int MOD = (int) (Math.pow(10, 9) + 7);

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        // 【Solution 1】暴力递归
//        return process1(m, n, maxMove, startRow, startColumn);
        
        // 【Solution 2】傻缓存
       // int[][][] dp = new int[maxMove + 1][m][n];
       // for (int move = 1; move <= maxMove; move++) { // 剩余步数move=0时，dp表内的位置均不存在paths
       //     for (int i = 0; i < m; i++) {
       //         Arrays.fill(dp[move][i], -1);
       //     }
       // }
       // return process2(m, n, maxMove, startRow, startColumn, dp);
        
        // 【Solution 3】dp
        int[][][] dp = new int[maxMove + 1][m][n];
        for (int move = 1; move <= maxMove; move++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int path = 0;
                    path += (i - 1 < 0) ? 1 : dp[move - 1][i - 1][j]; path %= MOD;
                    path += (i + 1 == m) ? 1 : dp[move - 1][i + 1][j]; path %= MOD;
                    path += (j - 1 < 0) ? 1 : dp[move - 1][i][j - 1]; path %= MOD;
                    path += (j + 1 == n) ? 1 : dp[move - 1][i][j + 1]; path %= MOD;
                    dp[move][i][j] = path;
                }
            }
        }
        return dp[maxMove][startRow][startColumn];
    }

//     public int process1(int m, int n, int remain, int i, int j) {
//         if (remain < 0) return 0;
//         if (i == m || j == n || i < 0 || j < 0) return 1;
//         return process1(m, n, remain - 1, i + 1, j) +
//                 process1(m, n, remain - 1, i - 1, j) +
//                 process1(m, n, remain - 1, i, j + 1) +
//                 process1(m, n, remain - 1, i, j - 1);
//     }

//     public int process2(int m, int n, int remain, int i, int j, int[][][] dp) {
//         if (remain < 0) return 0;
//         if (i == m || j == n || i < 0 || j < 0) return 1;
//         if (dp[remain][i][j] >= 0) return dp[remain][i][j];
//         dp[remain][i][j] = process2(m, n, remain - 1, i + 1, j, dp) % (MOD);
//         dp[remain][i][j] += process2(m, n, remain - 1, i - 1, j, dp); dp[remain][i][j] %= MOD;
//         dp[remain][i][j] += process2(m, n, remain - 1, i, j + 1, dp); dp[remain][i][j] %= MOD;
//         dp[remain][i][j] += process2(m, n, remain - 1, i, j - 1, dp); dp[remain][i][j] %= MOD;
//         return dp[remain][i][j];
//     }
}