骑士在棋盘上的概率

骑士在棋盘上的概率(medium)

做题过程

我认为用dfs或者bfs都可以解决这个问题，无非就是累加然后做除法，但结果发现，深度优先搜索占用的线程将会 指数级上升 ，类似一个多叉树结构同时遍历，而不是逐个子树自顶到底，然后再回到根节点，而且无法完成这一过程，因为 不知道有多少步 ，所以会引发 多线程更新彼此冲突覆盖 的问题。所以还是要用动态规划，一个一个子问题的走。

算法概述

原题

本题要求为给出骑士在棋盘上的起始位置以及移动步数，给出过了一定步数后骑士仍在棋盘上的概率。使用 动态规划 计算每个子问题的 概率结果 ，直接加到答案上。

• 时间复杂度为：每个都要遍历
• 空间复杂度为：dp临时三维数组

JAVA

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) {
        // 三维动态规划，注意数据长度设置为k+1，便于处理边界
        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];
    }
}

总结

就是要 避开常规思路的陷阱 ：直接统计可能总数，用除法计算。理解并熟练掌握动态规划的思路，找到状态转移方程的合理存在，我觉得核心就是 有没有在部分属性上一样的结构 和 结构之间是否有规律的相对关系 ，而且要记住的是 子问题直接导向目标变量 ，不会计算临时变量。

这个看似是三维（多维）动态规划，实际上还是一般的动态规划问题。