骑士在棋盘上的概率——dp棋盘概率题
目录
题目
题目详解
一个骑士有 $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];
}
};