688. Knight Probability in Chessboard

// LeetCode URL: https://leetcode.com/problems/knight-probability-in-chessboard/

/**
 * Dynamic Programming
 *
 * DP[i][j] = Probability of knight being moved here after K moves.
 *
 * Time Complexity: O(8 * K * N^2)
 *
 * Space Complexity: O(N^2)
 *
 * N = chess board size. K = Number of moves.
 */
class Solution {
    public double knightProbability(int N, int K, int r, int c) throws IllegalArgumentException {
        if (N <= 0 || K < 0 || r < 0 || c < 0) {
            throw new IllegalArgumentException("Invalid input");
        }
        if (r >= N || c >= N) {
            return 0.0;
        }
        if (K == 0) {
            return 1;
        }

        int[][] dirs = new int[][] { { -2, -1 }, { -2, 1 }, { 2, -1 }, { 2, 1 }, { 1, -2 }, { 1, 2 }, { -1, -2 },
                { -1, 2 } };

        double[][] dp = new double[N][N];
        dp[r][c] = 1.0;

        while (K > 0) {
            double[][] dpNew = new double[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (dp[i][j] > 0) {
                        for (int[] d : dirs) {
                            int row = i + d[0];
                            int col = j + d[1];
                            if (row < 0 || col < 0 || row >= N || col >= N) {
                                continue;
                            }
                            dpNew[row][col] += dp[i][j] / 8.0;
                        }
                    }
                }
            }
            dp = dpNew;
            K--;
        }

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