此类DP都是每一步用一个临时二维数组来记录状态

688 Knight Probability in Chessboard

memory search

class Solution {

    double[][][] hash = new double[101][26][26];

    public double knightProbability(int N, int K, int r, int c) {
        Map<Integer, Double> hash = new HashMap<>();

        return dfs(r, c, N, K) / Math.pow(8.0, K);

    }

    private double dfs(int row, int col, int N, int K){
        int[] x_move = {-2, -1, 1, 2, 2, 1, -1, -2};
        int[] y_move = {1, 2, 2, 1, -1, -2, -2, -1};

        //System.out.println("before " + "row: " + row + " col: " + col + " K: " + K + " hash: " + hash);

        if (row < 0 || row >= N || col < 0 || col >= N) return 0.0;

        if (K == 0) return 1.0;

        int val = row * N + col;
        if (hash[K][row][col] > 0.0) return hash[K][row][col];

        double ans = 0.0;
        for (int i = 0; i < 8; i++){
            int rowrow = row + x_move[i];
            int colcol = col + y_move[i];

            //System.out.println("debug: " + (rowrow * N + colcol) + " row: " + rowrow + " col: " + colcol);

            ans += dfs(rowrow, colcol, N, K - 1);
        }
        hash[K][row][col] = ans;
        //System.out.println("after " + "row: " + row + " col: " + col + " K: " + K + " hash: " + hash);

        return ans;
    }
}

DP

class Solution {
    public double knightProbability(int N, int K, int r, int c) {
        double[][] dp = new double[N][N];

        dp[r][c] = 1.0;

        int[] x_move = {-2, -1, 1, 2, 2, 1, -1, -2};
        int[] y_move = {1, 2, 2, 1, -1, -2, -2, -1};

        for (; K > 0; K--){
            double[][] dp2 = new double[N][N];
            for (int row = 0; row < N; row++){
                for (int col = 0; col < N; col++){
                    for (int i = 0; i < 8; i++){
                        int rowrow = row + x_move[i];
                        int colcol = col + y_move[i];

                        if (rowrow < 0 || rowrow >= N || colcol < 0 || colcol >= N) continue;

                        dp2[rowrow][colcol] += dp[row][col] / 8.0;
                    }            
                }
            }
            dp = dp2;
        }

        double ans = 0.0;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                ans += dp[i][j];
            }
        }

        return ans;
    }
}

576 Out of Boundary Paths

class Solution {
    private static final int C = 1000000007;
    public int findPaths(int m, int n, int N, int i, int j) {
        int[][] dp = new int[m][n];
        dp[i][j] = 1;

        int count = 0;
        int[] x_move = {0, 1, 0, -1};
        int[] y_move = {1, 0, -1, 0};
        for (int k = 1; k <= N; k++){
            int[][] dp2 = new int[m][n];

            for (int row = 0; row < m; row++){
                for (int col = 0; col < n; col++){
                    for (int t = 0; t < 4; t++){
                        int rowrow = row + x_move[t];
                        int colcol = col + y_move[t];

                        if (rowrow < 0 || rowrow >= m || colcol < 0 || colcol >= n){
                            count = (count + dp[row][col]) % C;
                            continue;
                        }

                        dp2[rowrow][colcol] = (dp2[rowrow][colcol] + dp[row][col]) % C;
                    }
                }
            }

            dp = dp2;
        }

        return count;
    }
}