688. Knight Probability in Chessboard - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
        DIR = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
        memo = [[[-1] * N for i in range(N)] for j in range(K)]
        
        def helper(row, col, count):
            if row < 0 or row >= N or col < 0 or col >= N:
                return 0
            
            if count == K:
                return 1
            
            if memo[count][row][col] >= 0:
                return memo[count][row][col]
            
            res = 0
            for x, y in DIR:
                res += 0.125 * helper(row+x, col+y, count+1)
            
            memo[count][row][col] = res
            return res
        
        return helper(r, c, 0)