leetcode688. 骑士在棋盘上的概率
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/knight-probability-in-chessboard
题目描述
在一个 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 - 1
解题思路
递归去解决这个问题。八个方向递归。
每次走步数减一。
base case .步数为0 时,和走出棋盘时,都停止,
注意:
直接暴力递归,会超时,跑不过去,需要加上缓存,
代码演示
public double knightProbability(int n, int k, int row, int column) {
double[][][]dp = new double[n][n][k+1];
return process(n,k,row,column,dp);
}
public double process(int n ,int k,int row,int column,double[][][]dp){
//抛出棋盘外,直接停止
if(row >= n || row < 0 || column >= n || column < 0){
return 0.0;
}
//缓存有值时 从缓存里拿值
if( dp[row][column][k] != 0){
return dp[row][column][k];
}
//步数走完,走出棋盘外的情况已经在上面拦截,到这里的都是棋盘内的,直接返回1
if(k == 0){
return 1.0;
}
double ori = 0.125;
//八个方向递归
double p1 = ori * process(n,k-1,row-2,column+1,dp);
p1 += ori * process(n,k-1,row-1,column+2,dp);
p1 += ori * process(n,k-1,row+1,column+2,dp);
p1 += ori * process(n,k-1,row+2,column+1,dp);
p1 += ori * process(n,k-1,row+2,column-1,dp);
p1 += ori * process(n,k-1,row+1,column-2,dp);
p1 += ori * process(n,k-1,row-1,column-2,dp);
p1 += ori * process(n,k-1,row-2,column-1,dp);
dp[row][column][k] = p1;
return p1;
}
动态规划专题
leetcode.486. 预测赢家
leetcode1143. 最长公共子序列
最长回文子序列
象棋里马走到指定位置的方法数
最小路径和文章来源:https://www.toymoban.com/news/detail-476533.html
凑零钱.钱币的组合有多少种文章来源地址https://www.toymoban.com/news/detail-476533.html
到了这里,关于leetcode688. 骑士在棋盘上的概率(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!