Problem statement

https://binarysearch.com/problems/Knight-Remains/

Solution

Equal to Leetcode 0688 Knight Probability in Chessboard.

Complexity

Time complexity is O(8n^2K), space complexity is O(n^2K)

Code

class Solution:
    def solve(self, N, r, c, K):
        dp = [[[0] * N for _ in range(N)] for _ in range(K+1)]
        dp[0][r][c] = 1
        neibs = [[1,2],[1,-2],[-1,2],[-1,-2],[2,1],[2,-1],[-2,1],[-2,-1]]
        for k,i,j in product(range(K),range(N),range(N)):
            for dx, dy in neibs:
                if 0 <= i+dx < N and 0 <= j+dy < N:
                    dp[k+1][i][j] += dp[k][i+dx][j+dy] / 8
        
        return int(sum(chain(*dp[-1])) * 100)