为什么棋盘中骑士概率的解法是错误的？

Question

leetcode 的问题陈述 - https://leetcode.com/problems/knight-probability-in-chessboard/

基本上，骑士从给定的位置开始，随机选择 8 种可能的走法中的 1 种。它进行了 k 次这样的移动，我们需要找到它在 k 次移动结束时最终留在棋盘上的概率。它是均匀分布的，因此每次移动的概率为 1/8；

我的方法-

让我们想象一个没有循环且每个深度有 2 个有效移动的假设情况。它会长成这样一棵树-

所以概率是

 (1/8 * (prob(b) + prob(c)) where prob(b) and prob(c) each = 1/8 * (sum of children)

本质上，(1/8)^k * 叶子节点的数量。

现在我们考虑这些周期的周期和记忆 - 如果对于任何给定的节点 x，我们来寻找深度 k，那么该搜索末尾的叶节点将做出贡献

(1/8) ^ (k - kOfX)

.

例如，如果上面的树的图像实际上代表了一棵更大的树中的子树，那么我们可以想象以 k = 1 作为某个循环的一部分而不是 k = 2 到达 A。在计算 k = 2 时，我们可以使用父级和子级之间的深度差异来计算子级对其每个父级所做的贡献。因此直系子代将贡献 (1/8)^(k - (k -1)) = 1/8。每当我们访问一个节点时，我们都会使用这个公式更新它的所有父节点。

代码-

public class KnightProbabilityInChessboard {
    class Pair{
        int row, col;
        int k;
        Pair(int row, int col, int k){
            this.row = row;
            this.col = col;
            this.k = k;
        }

        Pair(int row, int col){
            this.row = row;
            this.col = col;
        }
    }
    //Flow starts from here. This is the execution point
    public double knightProbability(int n, int k, int row, int column) {
        int isVisited[][] = new int[n][n];
        double value[][][] = new double[n][n][k + 1];
        knightProbabilitycalc2(k , value, isVisited, row, column, new ArrayList<>());
        return value[row][column][k];
    }

    //main logic
    void knightProbabilitycalc2(int k, double value[][][], int visited[][], int row, int column, List<Pair> parents) {

         //memozied block. IF a node is visited we store the depth of pre existing calculation
        if (visited[row][column] > k && k!= 0) {
            for(int i = parents.size() - 1; i >= 0; --i){
                Pair parent = parents.get(i);
                double res =  Math.pow((1/8.0), parent.k - k - 1) * value[row][column][k];
                value[parent.row][parent.col][parent.k - k] += res;
            }
            return;
        }

        //if not the last move in sequence then search deeper
        if(k != 0) {
            int n = value.length;
            List<Pair> validMoves = getAllMoves(row, column).stream().filter((move) -> isValid(move.row, move.col, n - 1, n - 1)).collect(Collectors.toList());
            parents.add(new Pair(row, column, k));
            for (Pair move : validMoves) {
                knightProbabilitycalc2(k - 1, value, visited, move.row, move.col, parents);
            }
            parents.remove(parents.size() - 1);
        }

        //after search is over, update all of its parents using the aforementioned forumla
        for(int i = parents.size() - 1; i >= 0; --i){
            Pair parent = parents.get(i);
            double res =  Math.pow((1/8.0), parent.k - k);
            value[parent.row][parent.col][parent.k - k] += res;
        }
        // all possible values of values[row][column][index<=k] have been calculated.
        visited[row][column] = k;
    }


    List<Pair> getAllMoves(int row, int col){
        List<Pair> validMoves = new ArrayList<>();
        validMoves.add(new Pair(row - 2, col - 1));
        validMoves.add(new Pair(row - 2, col + 1));
        validMoves.add(new Pair(row + 2, col + 1));
        validMoves.add(new Pair(row + 2, col - 1));
        validMoves.add(new Pair(row + 1, col - 2));
        validMoves.add(new Pair(row + 1, col + 2));
        validMoves.add(new Pair(row - 1, col - 2));
        validMoves.add(new Pair(row - 1, col + 2));
        return validMoves;
    }

    boolean isValid(int r, int c, int maxR, int maxC){
        return (0 <= r &&  r <= maxR  && 0 <= c && c <= maxC);
    }

对于不同的 n 值，此代码适用于 k = 3 之前的情况，但对于简单情况，从 4 开始就失败了。我怀疑这是因为循环逻辑。此外，它还大大低估了结果。对于 k = 30、n = 8，预期输出为 0.0019，而我的输出为 e-25 规模。

我可以确认移动生成和有效性检查都很好。它适用于所有情况 k <= 3

我知道有自下而上的方法，但我想了解为什么这行不通。这就是为什么我觉得它与关于这个特定问题的其他问题不同。它重点关注实施困难。

Answer 1

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

    double[][] dp = new double[n][n];
    dp[row][column] = 1.0;

    for (int move = 1; move <= k; move++) {
        double[][] nextDp = new double[n][n];

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                for (int[] dir : directions) {
                    int nr = r + dir[0];
                    int nc = c + dir[1];

                    if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                        nextDp[nr][nc] += dp[r][c] / 8.0;
                    }
                }
            }
        }

        dp = nextDp;
    }

    double probability = 0.0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            probability += dp[r][c];
        }
    }

    return probability;
}

}

这是来自

的解决方案

聊天GPT

，也许你可以分析这种方法并实现你的目标，祝你有美好的一天）