力扣 688. 骑士在棋盘上的概率

题目来源:https://leetcode-cn.com/problems/knight-probability-in-chessboard/
大致题意: 给一个 n*n 的矩阵棋盘和棋子的起始位置,棋子按照国际象棋规则移动,求出 k 次移动后仍在棋盘上的概率
思路
反向思考,起始位置 k 次移动后仍在棋盘上的概率可以转化为从棋盘上任意一个位置移动 k 次到达起始位置的概率
于是可以使用动态规划来解题
动态规划
使用 dp[s][i][j] 表示第 s 步移动到位置 (i, j) 的概率初始时,即 s 为 0 时,所有的概率为 1更新时, dp[s][i][j] 为所有 dp[s - 1][x][y] / 8 的和,其中 (x, y) 即为可以移动到 (i, j) 的位置
代码
public double knightProbability(int n, int k, int row, int

力扣 688. 骑士在棋盘上的概率最先出现在Python成神之路

版权声明:
作者:cc
链接:https://www.techfm.club/p/22575.html
来源:TechFM
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>