江西建设职业技能教育咨询网站,重庆网站建设外贸,档案网站建设书,最新旅游新闻播报题目描述
原题链接#xff1a;Leetcode. 688骑士在棋盘上的概率
解题思路
多元dp
将dp[step][i][j])定义为从(i, j)出发#xff0c;走step步之后骑士还在棋盘上的概率。
如果 ( i , j ) (i,j) (i,j)不在棋盘上#xff0c;即非 0 i n 0in 0i…题目描述
原题链接Leetcode. 688骑士在棋盘上的概率
解题思路
多元dp
将dp[step][i][j])定义为从(i, j)出发走step步之后骑士还在棋盘上的概率。
如果 ( i , j ) (i,j) (i,j)不在棋盘上即非 0 i n 0in 0in或者非 0 j n 0jn 0jn那么此时概率一定为 0 0 0。如果 s t e p 0 step0 step0那么这个时候骑士已经无需再走而且经过上面的判断骑士此时一定在棋盘上所以经过 0 0 0步之后骑士一定还在棋盘上此时概率为 1 1 1。如果不满足上述的条件那么此时考虑 d p [ s t e p ] [ i ] [ j ] dp[step][i][j] dp[step][i][j]从 d p [ s t e p − 1 ] [ i − d x ] [ j − d y ] dp[step-1][i-dx][j-dy] dp[step−1][i−dx][j−dy]转化而来其中 d x dx dx和 d y dy dy是骑士能走的在 x x x方向和 y y y方向上的位移大小。由题意可知一共有八个方向可以到达 ( i , j ) (i,j) (i,j)那么从每个点过来的概率就是 1 8 \frac{1}{8} 81。也就是说 d p [ s t e p ] [ i ] [ j ] ∑ 1 8 d p [ s t e p − 1 ] [ i − d x ] [ j − d y ] dp[step][i][j]\sum \frac{1}{8}dp[step-1][i-dx][j-dy] dp[step][i][j]∑81dp[step−1][i−dx][j−dy]
python代码
class Solution:def knightProbability(self, n: int, k: int, row: int, column: int) - float:dx [-1,-2,-2,-1,1,2,2,1]dy [-2,-1,1,2,2,1,-1,-2]cachedef dfs(k, i, j):if not (0 i n and 0 j n):return 0if k 0:return 1.return sum(dfs(k-1, ixx, jyy) for xx,yy in zip(dx, dy))/8 return dfs(k, row, column)
