比价网站 源码德芙巧克力软文推广
题目描述
原题链接：Leetcode. 688骑士在棋盘上的概率
解题思路
多元dp
将dp[step][i][j])定义为从(i, j)出发，走step步之后骑士还在棋盘上的概率。
- 如果 ( i , j ) (i,j) (i,j)不在棋盘上，即非 0 < = i < n 0<=i<n 0<=i<n或者非 0 < = j < n 0<=j<n 0<=j<n，那么此时概率一定为 0 0 0。
- 如果 s t e p = 0 step=0 step=0，那么这个时候骑士已经无需再走，而且经过上面的判断，骑士此时一定在棋盘上，所以经过 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, i+xx, j+yy) for xx,yy in zip(dx, dy))/8 return dfs(k, row, column)