Leetcode. 688骑士在棋盘上的概率

题目描述

原题链接：Leetcode. 688骑士在棋盘上的概率

解题思路

多元dp

将dp[step][i][j])定义为从(i, j)出发，走step步之后骑士还在棋盘上的概率。

• 如果$(i,j)$不在棋盘上，即非$0<=i<n$或者非$0<=j<n$，那么此时概率一定为$0$。
• 如果$step=0$，那么这个时候骑士已经无需再走，而且经过上面的判断，骑士此时一定在棋盘上，所以经过$0$步之后骑士一定还在棋盘上，此时概率为$1$。
• 如果不满足上述的条件，那么此时考虑$dp[step][i][j]$从$dp[step-1][i-dx][j-dy]$转化而来，其中$dx$和$dy$是骑士能走的在$x$方向和$y$方向上的位移大小。由题意可知一共有八个方向可以到达$(i,j)$，那么从每个点过来的概率就是$\frac{1}{8}$。也就是说$dp[step][i][j]=\sum \frac{1}{8}dp[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)