【Day 59 】2022-12-29 - 688. “马”在棋盘上的概率

[azl397985856]

688. “马”在棋盘上的概率

入选理由

暂无

题目地址

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

前置知识

• 动态规划
• 数组

  题目描述

  
  已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。 

现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。 

如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。

现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。

求移动结束后，“马” 仍留在棋盘上的概率。

[Ryanbaiyansong]

··· class Solution: def knightProbability(self, n: int, m: int, r: int, c: int) -> float: // # n * n 的棋盘, 马尝试k步骤, //# 有8种可能的移动 //# 概率: (i, j) in 即 0 <= i < n and 0 <= j < n 的概率 //# f[i][j][k] 代表通过k步骤 从r, c 到达i,j的概率 /#/ 上一步有八个方向 /#/ 上一步的八个方向的概率 相加 = 当前的概率 /#/ 初始化: f[r][c][0] = 1 /#/ ans: f[i][j][k] for i in range(n) for j in range(n) DIRS = [(1,2), (1,-2), (-1,2), (-1,-2), (2, 1), (-2, 1), (2,-1), (-2, -1)]

    f = [[[0] * (m+1) for _ in range(n)] for _ in range(n)]
    f[r][c][0] = 1
    //# 对于这种乱七八糟不知道在哪的, 注意枚举位置
    for k in range(1, m + 1):
        for i in range(n):
            for j in range(n):
                for di, dj in DIRS:
                    x, y = i - di, j - dj
                    if 0 <= x < n and 0 <= y < n:
                        f[i][j][k] += f[x][y][k-1]/ 8

    return sum(f[i][j][m] for i in range(n) for j in range(n))

···

[snmyj]

class Solution(object):
    def knightProbability(self, N, K, r, c):
        """
        :type N: int
        :type K: int
        :type r: int
        :type c: int
        :rtype: float
        """
        dp = [[0 for i in range(N)] for j in range(N)]
        dp[r][c] = 1
        directions = [(1, 2), (1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1), (-1, 2), (-1, -2)]
        for k in range(K):
            new_dp = [[0 for i in range(N)] for j in range(N)]
            for i in range(N):
                for j in range(N):
                    for d in directions:
                        x, y = i + d[0], j + d[1]
                        if x < 0 or x >= N or y < 0 or y >= N:
                            continue
                        new_dp[i][j] += dp[x][y]
            dp = new_dp
        return sum(map(sum, dp)) / float(8 ** K)

[yuxiangdev]

Intuition

From every cell on the chessboard, there are only eight directions we can go. Therefore, we can use a DP array to store the probability to reach each cell and update the probability Array step by step.

Approach

• Initialize an $$n*n$$ array $$dp$$ lastStep, to store the probability to reach each cell, where lastStep[row][column] is set to be 1 because that is starting state.

• Update the array step by step ($$k$$ steps in total), for each step, use a new $$n*n$$ array currentStep to represent the current step probability. (Use two seperate arrays because otherwise the probability of reaching [row][col] will be greater than 1)

• Updating rule is : for each of the 8 directions:

  • currentRow = previousRow + dir[0]
  • currentColumn = previousColumn + dir[1]
  • If cuurentRow or currentColumn is out of the board, skip.
  • Otherwise: currentStep[currentRow][currentColumn] += lastStep[previousRow][previousColumn] Therefore, the probability in each cell of currentStep is a sum of the probabilities from all the cells that are one step before.

• After each step, assign lastStep to be currentStep

• Sum all the probabilities within the lastStep array

  Complexity

• Time complexity: $$O(kn^2)$$

• Space complexity: $$O(n^2)$$

Code

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {-1, -2}, {1, -2}, {-2, -1}};
        double[][] lastStep = new double[n][n];
        lastStep[row][column] = 1;

        for (; k > 0; k--) {
            double[][] currentStep = new double[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x < 0 || x >= n || y < 0 || y >= n) continue;
                        currentStep[x][y] += lastStep[i][j] / 8.0;
                    }
                }
            }
            lastStep = currentStep;
        }

        double res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res += lastStep[i][j];
            }
        }

        return res;
    }
}

[heng518]

class Solution { public: double knightProbability(int n, int k, int row, int column) { vector<vector> dp(n, vector(n, 0)); vector dx = {2, 2, 1, 1, -1, -1, -2, -2}; vector dy = {1, -1, 2, -2, -2, 2, 1, -1}; double res = 0; dp[row][column] = 1;

    while(k > 0)
    {
        vector<vector<double>> dp2(n, vector<double>(n, 0));
        for(int x = 0; x < n; x++)
        {
            for(int y = 0; y < n; y++)
            {
                for(int k = 0; k < 8; k++)
                {
                    int new_x = x + dx[k];
                    int new_y = y + dy[k];
                    if(new_x >= 0 && new_x < n && new_y >= 0 && new_y < n)
                    {
                        dp2[new_x][new_y] += dp[x][y] / 8.0;
                    }
                }
            }
        }
        dp = dp2;
        k--;
    }
    for(auto vec:dp)
        for(auto value:vec)
            res += value;

    return res;
}

};

[zjsuper]

class Solution: def knightProbability(self, n: int, k: int, row: int, column: int) -> float: ans = [[0 for in range(n)] for in range(n)] ans[row][column] = 1 dic = [(-2,1),(-1,2),(1,2),(2,1),(-2,-1),(-1,-2),(1,-2),(2,-1)] for in range(k): ans2 = [[0 for in range(n)] for _ in range(n)] for r in range(n): for c in range(n): for k,v in dic: if r+k>-1 and r+k<n and c+v>-1 and c+v<n: ans2[r+k][c+v] += 0.125*ans[r][c] ans = ans2

    return sum([sum(i) for i in ans])

[ringo1597]

代码

class Solution {
    static int[][] dirs = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};

    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[k + 1][n][n];
        for (int step = 0; step <= k; step++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (step == 0) {
                        dp[step][i][j] = 1;
                    } else {
                        for (int[] dir : dirs) {
                            int ni = i + dir[0], nj = j + dir[1];
                            if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                            }
                        }
                    }
                }
            }
        }
        return dp[k][row][column];
    }
}

[whoam-challenge]

class Solution: def knightProbability(self, n: int, k: int, row: int, column: int) -> float: dp = [[[0] * n for in range(n)] for in range(k + 1)] for step in range(k + 1): for i in range(n): for j in range(n): if step == 0: dp[step][i][j] = 1 else: for di, dj in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)): ni, nj = i + di, j + dj if 0 <= ni < n and 0 <= nj < n: dp[step][i][j] += dp[step - 1][ni][nj] / 8 return dp[k][row][column]

[JancerWu]

class Solution {
    int[][] move = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
    double[][][] f;
    public double knightProbability(int n, int k, int row, int column) {
        f = new double[n][n][k];
        return dfs(n, 0, k, row, column);
    }

    public double dfs(int n, int cnt, int k, int i, int j) {
        if (i < 0 || j < 0 || i >= n || j >= n) {
            return 0;
        }
        if (cnt == k) {
            return 1.0;
        }
        if (f[i][j][cnt] != 0) {
            return f[i][j][cnt];
        }
        double ans = 0;
        for (int[] mv : move) {
            ans += dfs(n, cnt + 1, k, i + mv[0], j + mv[1]) / 8.0;
        }
        f[i][j][cnt] = ans; 
        return ans;
    }
}

[bookyue]

code

class Solution {
    private static final int[][] DIRS = new int[][]{{-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {-2, 1}, {-2, -1}, {2, 1}, {2, -1}};

    public double knightProbability(int n, int k, int row, int column) {
        return dfs(n, row, column, k, new double[n][n][k + 1]);
    }

    private double dfs(int n, int x, int y, int k, double[][][] memo) {
        if (x < 0 || x >= n || y < 0 || y >= n) return 0D;

        if (k == 0) return 1D;

        if (memo[x][y][k] != 0) return memo[x][y][k];

        double ans = 0D;

        for (int[] dir : DIRS) {
            ans += dfs(n, x + dir[0], y + dir[1], k - 1, memo) / 8D;
        }

        memo[x][y][k] = ans;
        return ans;
    }
}

[mayloveless]

思路

参考官方解答，每个格子计算出现概率，然后相加。出现概率是之前一步的八分之一，没走一次，测算一次全部格子的概率，累加

代码

var knightProbability = function(n, k, row, column) {
    const direction = [[-1, -2], [1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1]];
    let dp = Array(n).fill().map(() => Array(n).fill(0));
    dp[row][column] = 1;

    for(let x=0;x<k; x++) {
        const tempDp = Array(n).fill().map(() => Array(n).fill(0));
        for(let i=0;i<n;i++) {
            for(let j=0;j<n;j++) {
                for (let k = 0; k < 8; ++k) {
                    const newi = i + direction[k][0];
                    const newj = j + direction[k][1];
                    if (newi >= 0 && newi < n && newj >= 0 && newj < n) {
                        tempDp[i][j] += dp[newi][newj] * 0.125;// 叠加之前的概率
                    }
                }
            }
        }
        dp = [...tempDp];
    }

    // 累积所有格子的概率
    let res = 0;
    for(let i=0;i<n;i++) {
        for(let j=0;j<n;j++) {
            res += dp[i][j]
        }
    }
    return res;
};

复杂度

时间:O(n^2k8) 空间O(n^2)

[Abby-xu]

思路

抄答案DFS+DP

代码

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        dirs = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]

        @lru_cache(None)
        def sol(i, j, k):
            if k == 0:
                return 1
            curr = 0
            for di, dj in dirs:
                i2, j2 = i + di, j + dj
                if 0 <= i2 < n and 0 <= j2 < n:
                    curr += 0.125 * sol(i2, j2, k - 1)
            return curr

        return sol(row, column, k)

复杂度

O(n^2*k)

[chenming-cao]

解题思路

动态规划。参考题解。用二维数组储存到达该格子的概率。这里用到两个二维数组，dp用于储存移动之前的概率情况，dpTemp用于储存移动一步之后的概率状况。遍历二维数组dp，找到移动之前概率不为0的格子，由此格子出发找到8个可能到达的格子，如果新到达的格子坐标在范围（0 - n）中，说明格子在板子上，更新dpTemp数组中对应坐标的概率，加上dp / 8。遍历结束后，我们更新状态，dp = dpTemp。按照此方式循环k次，最后得到的dp数组中的概率值即为最终值。将所有概率值求和，最后即为棋子还在板子上的概率。

代码

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        // save the possible moving directions into an array
        int[][] dir = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};
        // use a 2D array to store the probability to move to the cell
        double[][] dp = new double[n][n];
        dp[row][column] = 1; // set the initial probability as 1

        // simulate the moving process, calculate the probability after each move, repeat for k times
        for (int step = 1; step <= k; step++) {
            // use a different 2D array to save the temporary probability after each move, easy to update
            // also we will need to refer to previous state to calculate the new state, 
            // we would not like to overwrite previous state
            double[][] dpTemp = new double[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    double prob = dp[i][j];
                    // only need to do the calculation starting from cell with probability > 0
                    if (prob > 0) {
                        // update the probability of 8 possible cells
                        for (int m = 0; m < 8; m++) {
                            int newRow = i + dir[m][0];
                            int newCol = j + dir[m][1];
                            // if still on the board after move, store probability results in dpTemp
                            if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n) {
                                dpTemp[newRow][newCol] += prob / 8;
                            }
                        }
                    }
                }
            }
            dp = dpTemp; // update dp when one move is done, status in dpTemp will be set as previous state
        }
        double res = 0; // use double here
        // calculate the total probability
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res += dp[i][j];
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(kn^2)，循环k次，每次遍历n*n的数组
• 空间复杂度：O(n^2)

[Elsa-zhang]

''' 688. 骑士在棋盘上的概率
'''

class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        step_proposed = [[2,-1], [2,1], [1,2], [-1,2], [-2,1], [-2,-1], [1,-2], [-1,-2]]
        dp = [[[0]*n for _ in range(n)] for _ in range(k+1)]
        for step in range(k+1):
            for i in range(n):
                for j in range(n):
                    if step == 0:
                        dp[step][i][j]=1
                    else:
                        for step_i, step_j in step_proposed:
                            if 0 <= i-step_i < n and 0 <= j-step_j < n:
                                dp[step][i][j] += (1/8)*dp[step-1][i-step_i][j-step_j]

        return dp[k][row][column]

[zywang0]

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {-1, -2}, {1, -2}, {-2, -1}};
        double[][] lastStep = new double[n][n];
        lastStep[row][column] = 1;

        for (; k > 0; k--) {
            double[][] currentStep = new double[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x < 0 || x >= n || y < 0 || y >= n) continue;
                        currentStep[x][y] += lastStep[i][j] / 8.0;
                    }
                }
            }
            lastStep = currentStep;
        }

        double res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res += lastStep[i][j];
            }
        }

        return res;
    }
}

[tiandao043]

思路

看了题解，每个格子放概率，累加。

代码

class Solution {
public:
    vector<vector<int>> dirs={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,2},{1,-2}};
    double knightProbability(int n, int k, int row, int column) {
        vector<vector<vector<double>>> dp(k+1,vector<vector<double>>(n,vector<double>(n)));
        // cout<<dp[0][1][1]<<endl;
        for(int s=0;s<=k;s++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(s==0)dp[s][i][j]=1;else{
                        for(auto&dir:dirs){
                        int ni=i+dir[0],nj=j+dir[1];
                        if(ni>=0&&ni<n&&nj>=0&&nj<n){
                            dp[s][i][j]+=dp[s-1][ni][nj]/8;
                        }
                    }
                    }

                }
            }
        }
        return dp[k][row][column];
    }
};

O(k×n^2)

[klspta]

超时版本

class Solution {

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

    public double knightProbability(int n, int k, int row, int column) {
        return dfs(n, k, row, column);
    }

    private double dfs(int n, int k, int i, int j){
        if(i < 0 || j < 0 || i >= n || j >= n){
            return 0;
        }
        if(k == 0){
            return 1;
        }

        double ans = 0;
        for(int[] d : dx){
            ans += dfs(n, k - 1, i + d[0], j + d[1]) / 8.0;
        }
        return ans;
    }
}

[klspta]

缓存加速

class Solution {

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

    public double knightProbability(int n, int k, int row, int column) {
        double[][][] cache = new double[n][n][k + 1];
        return dfs(n, k, row, column, cache);
    }

    private double dfs(int n, int k, int i, int j, double[][][] cache){
        if(i < 0 || j < 0 || i >= n || j >= n){
            return 0;
        }
        if(k == 0){
            return 1;
        }

        if(cache[i][j][k] != 0){
            return cache[i][j][k];
        }

        double ans = 0;
        for(int[] d : dx){
            ans += dfs(n, k - 1, i + d[0], j + d[1], cache) / 8.0;
        }
        cache[i][j][k] = ans;
        return ans;
    }
}

[A-pricity]

/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */
/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */
const DIRS = [[1, 2], [2, 1], [1, -2], [-2, 1], [2, -1], [-1, 2], [-1, -2], [-2, -1]]
var knightProbability = function(n, k, row, column) {
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(0).map(() => new Array(k + 1).fill(0)));
    for(let i = 0; i < n; i++)
        for(let j = 0; j < n; j++)
            dp[i][j][0] = 1
    for(let i = 1; i <= k; i++)
        for(let r = 0; r < n; r++)
            for(let c = 0; c < n; c++)
                for(const dir of DIRS) {
                    const nr = r + dir[0], nc = c + dir[1]
                    if(nr >= 0 && nr < n && nc >= 0 && nc < n){
                        dp[r][c][i] += dp[nr][nc][i - 1]/8
                    }
                }
    return dp[row][column][k]
};

[RestlessBreeze]

code

class Solution {
public:
    vector<vector<int>> dirs = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};

    double knightProbability(int n, int k, int row, int column) {
        vector<vector<vector<double>>> dp(k + 1, vector<vector<double>>(n, vector<double>(n)));
        for (int step = 0; step <= k; step++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (step == 0) {
                        dp[step][i][j] = 1;
                    } else {
                        for (auto & dir : dirs) {
                            int ni = i + dir[0], nj = j + dir[1];
                            if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                            }
                        }
                    }
                }
            }
        }
        return dp[k][row][column];
    }
};

[luhaoling]

class Solution {

private int[][] dir = {{-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) {

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

    for (int step = 1; step <= K; step++) {

        double[][] dpTemp = new double[N][N];

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                for (int[] direction : dir) {

                    int lastR = i - direction[0];
                    int lastC = j - direction[1];
                    if (lastR >= 0 && lastR < N && lastC >= 0 && lastC < N)
                        dpTemp[i][j] += dp[lastR][lastC] * 0.125;
                }

        dp = dpTemp;
    }

    double res = 0;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            res += dp[i][j];

    return res;
}

}

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        int[][] dirs = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
        double[][][] dp = new double[n][n][k + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][0] = 1;
            }
        }
        for (int z = 1; z <= k; z++) {
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    for (int i = 0; i < 8; i++) {
                        int dx = x + dirs[i][0], dy = y + dirs[i][1];
                        if (dx >= 0 && dx < n && dy >= 0 && dy < n) {
                            dp[x][y][z] += dp[dx][dy][z - 1] / 8;
                        }
                    }
                }
            }
        }
        return dp[row][column][k];
    }
}

[paopaohua]

class Solution {
    static int[][] dirs = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};

    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp = new double[k + 1][n][n];
        for (int step = 0; step <= k; step++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (step == 0) {
                        dp[step][i][j] = 1;
                    } else {
                        for (int[] dir : dirs) {
                            int ni = i + dir[0], nj = j + dir[1];
                            if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
                                dp[step][i][j] += dp[step - 1][ni][nj] / 8;
                            }
                        }
                    }
                }
            }
        }
        return dp[k][row][column];
    }
}

[Jetery]

code(java)

class Solution {

    private static final int[][] DIRS = {{1, 2}, {2, 1}, 
    {-1, 2}, {2, -1}, {1, -2}, {-2, 1}, {-1, -2}, {-2, -1}};

    public double knightProbability(int n, int k, int row, int column) {             
        double[][][] memo = new double[n][n][k + 1];
        return dfs(n, k, row, column, memo);
    }

    public double dfs(int n, int k, int i, int j, double[][][] memo) {
        // 走出边界
        if (i < 0 || j < 0 || i >= n || j >= n) {
            return 0;
        }
        // k 步走完了还没超出边界，这一步的概率是1，还需要乘上前面的 k 个 1/8
        if (k == 0) {
            return 1;
        }
        // 缓存中存在，直接返回
        if (memo[i][j][k] != 0) {
            return memo[i][j][k];
        }
        // 每一个方向的概率都是 1/8
        double ans = 0;
        for (int[] dir : DIRS) {
            ans += dfs(n, k - 1, i + dir[0], j + dir[1], memo) / 8.0;
        }
        memo[i][j][k] = ans;
        return ans;
    }
}

[FlipN9]

/**
    f[i][j][step]: 从 i, j 出发, 走不超过 step 步, 最后仍留在棋盘内的概率
    TC: O(N^2 * k * C) where C = 8 = O(N^2 * k)
    SC: O(N^2 * k)
*/
class Solution {
    static int[][] dirs = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};

    public double knightProbability(int N, int K, int row, int column) {
        double[][][] f = new double[N][N][K + 1];
        for (double[][] x : f)
            for (double[] y : x)
                y[0] = 1;
        for (int step = 1; step <= K; step++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int[] dir : dirs) {
                        int x = i + dir[0], y = j + dir[1];
                        if (x < 0 || x >= N || y < 0 || y >= N) continue;
                        f[i][j][step] += f[x][y][step - 1] / 8;
                    }
                }
            }
        }
        return f[row][column][K];
    }
}

[buer1121]

class Solution: def knightProbability(self, n: int, k: int, row: int, column: int) -> float:

定义状态：“马” 仍留在棋盘上的概率 dp[i][j]： 位置(i, j)有马的概率

    dp = [[0] * n for _ in range(n)]
    #初始化
    dp[row][column] = 1
    for _ in range(k):
        nxt = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                #dp记录当前概率，nxt记录移动一次以后的概率 nxt[x][y] += dp[i][j] / 8 其中，(x, y) 是移动后位置，(i, j)  
                #是移动前位置 也就是说 (i, j) 有1/8的概率移动到 (x, y)
                for x, y in ((i + 2, j + 1), (i + 2, j - 1), (i - 2, j + 1), (i - 2, j - 1), 
                            (i + 1, j + 2), (i - 1, j + 2), (i + 1, j - 2), (i - 1, j - 2)):
                    if 0 <= x < n and 0 <= y < n:
                        nxt[x][y] += dp[i][j] / 8
        dp = nxt
    return sum(map(sum, dp))