688. Knight Probability in Chessboard棋子留在棋盘上的概率

［抄题］：

On an NxN chessboard, a knight starts at the r-th row and c-th column and attempts to make exactly Kmoves. The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N-1, N-1).

A chess knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly K moves or has moved off the chessboard. Return the probability that the knight remains on the board after it has stopped moving.

Example:

Input: 3, 2, 0, 0
Output: 0.0625
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

以为就是数学题算一下就行了。没想到每走一步，棋盘都要变化，所以要用2个dp数组：初始和现在。

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［一句话思路］：

没想到每走一步，棋盘都要变化，所以要用2个dp数组：初始和现在。进行坐标型dp。

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

ij是新扩展的，row col是原来已有的。所以要用新扩展的+原来已有的。
答案要求小数时，初始化数组为double型。

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

没想到每走一步，棋盘都要变化，所以要用2个dp数组：初始和现在。

［复杂度］：Time complexity: O(n2) Space complexity: O(n2)

［算法思想：迭代/递归/分治/贪心］：

［关键模板化代码］：

二维矩阵需要一行行地填：

for (double[] row : dp0) {
            Arrays.fill(row, 1);
        }

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

[潜台词] ：

class Solution {
    int[][] directions = {{1, 2}, {1, -2}, {2, - 1}, {2, 1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};
    public double knightProbability(int N, int K, int r, int c) {
        //corner case
        
        //initialization: len, dp0[][] and fill with 1
        double[][] dp0 = new double[N][N];
        for (double[] row : dp0) {
            Arrays.fill(row, 1);
        }
        
        //calculate dp1, give to dp0
        for (int l = 0; l < K; l++) {
            double[][] dp1 = new double[N][N];
            for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int[] d : directions) {
                     int row = i + d[0];
                     int col = j + d[1];
                    if (valid(row, col, N)) dp1[i][j] += dp0[row][col];
                }
            }
        }
            dp0 = dp1;
        }
        return dp0[r][c] / (Math.pow(8, K));
    }
    
    public boolean valid(int x, int y, int len) {
        if (0 <= x && x < len && 0 <= y && y < len) return true;
        return false;
    }
}

View Code