### 题目描述 在一个** n x n **的国际象棋棋盘上，一个骑士从单元格** (row, column) **开始，并尝试进行** k **次移动。行和列是 从** 0 **开始 的，所以左上单元格是** (0,0)** ，右下单元格是** (n - 1, n - 1) **。  - 象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。 - 每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。 - 骑士继续移动，直到它走了 k 步或离开了棋盘。 - 返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。 ### 输入输出 #### 示例1 ``` 输入: n = 3, k = 2, row = 0, column = 0 输出: 0.0625 解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。 在每一个位置上，也有两种移动可以让骑士留在棋盘上。 骑士留在棋盘上的总概率是0.0625。 ``` #### 示例2 ``` 输入: n = 1, k = 0, row = 0, column = 0 输出: 1.00000 ``` **提示:** - 1 <= n <= 25 - 0 <= k <= 100 - 0 <= row, column <= n ### 题目解答 #### 思路 对该问题采用dp的思想，使用dp[step][i][j]记录，跳step步骤，到位置(i,j)的概率大小。 **情况1** 当step=0的时候，我们将所有位置概率初始化成1，这样当选中$$dp[0][row][col]$$时候,返回的概率就为1; **情况2** 当step>0的时候，该位置的概率，根据step-1周围8个位置的概率求和所得的0.125。 对于状态转移方程如下所示： $$dp[step][i][j] = \frac{1}{8} \sum_{(di,dj)}dp[step-1][i+d_i][j+d_j]$$ 其中$$(d_i,d_j)$$如下所示: $$(d_i, d_j) \in \lbrace (-2,-1),(-2,1),(2,-1),(2,1),(-1,2),(-1,-2),(1,2),(1,-2)\rbrace $$ **算法复杂度** 设棋盘的长和宽为n，步数为k。 时间复杂度：采用3重循环，获得dp矩阵，因此计算矩阵的时间复杂度的$$O(n^2k)$$ 空间复杂度：需要dp矩阵记录，空间复杂度也是$$O(n^2k)$$ 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复