题目 题目链接 题目描述题目详解 一个骑士有 $8$ 种可能的走法，骑士会从中以等概率随机选择一种。部分走法可能会让骑士离开棋盘，另外的走法则会让骑士移动到棋盘的其他位置，并且剩余的移动次数会减少 1。 定义 $dp[step][i][j]$ 表示其实从棋盘商店的点 $(i,j)$ 出发，走了 $step$ 步时仍然留在棋盘上的概率。当点 $(i,j)$ 不在棋盘上的时候，$dp[step][i][j] = 0;$当点 $(i,j)$ 在棋盘上且 $step = 0$ 时，$dp[step][i][j]=1$ 。对于其他情况，$dp[step][i][j]=1/8×∑dp[step-1][i+di][j+dj]$。 其中$(di,dj)$ 表示走法对坐标的偏移量，具体为 $(−2,−1),(−2,1),(2,−1),(2,1),(−1,−2),(−1,2),(1,−2),(1,2)$ 共 $8$ 种。解题代码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]; } };