688.md

688 Knight Probability in Chessboard

Description

link

---

Solution 1 : DP

dp[i][j] : the probability (times not rate) that the knight remains on the board after it has stopped moving (starts from (i, j))

Recursive : dp[i][j] += dp[x][y] for all x, y on the board and can move one step to (i, j)

Init : dp[i][j] = 1 when K = 0

---

Solution 2 : DFS + MEMO

key : (k, i, j)

---

Code 1

Complexity T : O(KN^2) M : O(N^2)

class Solution:
    def knightProbability(self, N, K, r, c):
        """
        :type N: int
        :type K: int
        :type r: int
        :type c: int
        :rtype: float
        """
        dp = [[1] * N for _ in range(N)]
        dirs = [[1, 2], [1, -2], [-1, -2], [-1, 2], [2, 1], [2, -1], [-2, -1], [-2, 1]]
        
        for k in range(K):
            t = [[0] * N for _ in range(N)]
            for i in range(N):
                for j in range(N):
                    for dir in dirs:
                        x, y = i + dir[0], j + dir[1]
                        if x >= 0 and x <= N - 1 and y >= 0 and y <= N - 1:
                            t[i][j] += dp[x][y]
            dp = t
        
        return dp[r][c] / 8 ** K

---

Code 2

Complexity T : O(KN^2) M : O(N^2)

class Solution:
    def knightProbability(self, N, K, r, c):
        """
        :type N: int
        :type K: int
        :type r: int
        :type c: int
        :rtype: float
        """
        dirs = [[1, 2], [1, -2], [-1, -2], [-1, 2], [2, 1], [2, -1], [-2, -1], [-2, 1]]
        
        memo = collections.defaultdict(float)
        
        def dfs(k, i, j):
            if k == 0: return 1.0
            if (k, i, j) in memo:return memo[(k, i, j)]
            
            for dir in dirs:
                x, y = i + dir[0], j + dir[1]
                if x >= 0 and x <= N - 1 and y >= 0 and y <= N - 1:
                    memo[(k, i, j)] += dfs(k - 1, x, y)
            
            return memo[(k, i, j)]
        
        return dfs(K, r, c) / 8 ** K