688. 骑士在棋盘上的概率

本文主要是介绍688. 骑士在棋盘上的概率，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: 688. 骑士在棋盘上的概率

思路

这是一个动态规划问题。我们需要计算骑士在棋盘上移动k次后仍然留在棋盘上的概率。骑士的每一步都有8种可能的移动方式，因此我们可以使用一个三维数组dp[i][j][k]来存储骑士在第k步时位于棋盘的(i, j)位置的概率。

解题方法

初始化一个三维数组dp，其中dp[i][j][k]表示骑士在第k步时位于棋盘的(i, j)位置的概率。初始时，所有的dp[i][j][k]都设为-1，表示未计算。
定义一个递归函数f，用于计算骑士在第k步时位于棋盘的(i, j)位置的概率。如果(i, j)位置不在棋盘上，那么概率为0；如果k为0，那么概率为1；否则，概率为骑士从(i, j)位置移动到棋盘上的其他位置的概率之和，每种移动方式的概率都是1/8。
在递归函数f中，如果dp[i][j][k]不为-1，那么直接返回dp[i][j][k]，否则计算dp[i][j][k]的值，并将其存入dp数组中。
最后，返回dp[row][col][k]，即骑士在第k步时位于棋盘的(row, col)位置的概率。

复杂度

时间复杂度:

由于我们需要计算每个位置在每一步的概率，所以时间复杂度为 $O(n^2\ast k)$，其中 $n$ 为棋盘的大小，$k$ 为移动的步数。

空间复杂度:

我们使用了一个三维数组 $dp$ 来存储每个位置在每一步的概率，所以空间复杂度为 $O(n^2\ast k)$。

Code

class Solution {public double knightProbability(int n, int k, int row, int col) {double[][][] dp = new double[n][n][k + 1];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {for (int t = 0; t <= k; t++) {dp[i][j][t] = -1;}}}return f(n, row, col, k, dp);}public double f(int n, int i, int j, int k, double[][][] dp) {if (i < 0 || i >= n || j < 0 || j >= n) {return 0;}if(dp[i][j][k] != -1) {return dp[i][j][k];}double ans = 0;if (k == 0) {ans = 1;} else {ans += (f(n, i - 2, j + 1, k - 1, dp) / 8);ans += (f(n, i - 1, j + 2, k - 1, dp) / 8);ans += (f(n, i + 1, j + 2, k - 1, dp) / 8);ans += (f(n, i + 2, j + 1, k - 1, dp) / 8);ans += (f(n, i + 2, j - 1, k - 1, dp) / 8);ans += (f(n, i + 1, j - 2, k - 1, dp) / 8);ans += (f(n, i - 1, j - 2, k - 1, dp) / 8);ans += (f(n, i - 2, j - 1, k - 1, dp) / 8);}dp[i][j][k] = ans; return ans;}
}

这篇关于688. 骑士在棋盘上的概率的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---