688. Knight Probability in Chessboard

 一刷 06/2022

Version #1 DP

Time O(8N^2 * K) ~ O(KN^2)

Space O(N^2)

Runtime: 13 ms, faster than 40.31% of Java online submissions for Knight Probability in Chessboard.

Memory Usage: 41.7 MB, less than 83.76% of Java online submissions for Knight Probability in Chessboard.

class Solution {

    private static int[] dx = new int[]{2, 2, 1, -1, -2, -2, -1, 1};

    private static int[] dy = new int[]{1, -1, -2, -2, -1, 1, 2, 2};

    public double knightProbability(int n, int k, int row, int column) {

        double[][][] probability = new double[2][n][n];

        probability[0][row][column] = 1.0;

        for (int i = 1; i <= k; i++) {

            for (int y = 0; y < n; y++) {

                for (int x = 0; x < n; x++) {

                    int z = i % 2;

                    int prevZ = (i - 1) % 2;

                    probability[z][y][x] = 0.0;

                    // current position can collect probability from 8 directions

                    for (int j = 0; j < 8; j++) {

                        int nx = x + dx[j];

                        int ny = y + dy[j];

                        if (nx < 0 || ny < 0 || nx >= n || ny >= n) {

                            continue;

                        }

                        probability[z][y][x] += probability[prevZ][ny][nx] / 8.0;

                    }

                }

            }

        }

        double result = 0.0;

        int z = k % 2;

        for (int y = 0; y < n; y++) {

            for (int x = 0; x < n; x++) {

                result += probability[z][y][x];

            }

        }

        return result;

    }

}