Python recursive solution with cache


  • 0
    L
    class Solution:
        def work(self, N, K, r, c, onboard, cache):
            offboard = r < 0 or c < 0 or r >= N or c >= N
            if K == 0 or offboard:
                if not offboard:
                    onboard += 1
                return onboard
            if (K, r, c) in cache:
                return cache[(K, r, c)]
    
            count = self.work(N, K - 1, r + 1, c + 2, onboard, cache) + \
                self.work(N, K - 1, r + 1, c - 2, onboard, cache) + \
                self.work(N, K - 1, r - 1, c + 2, onboard, cache) + \
                self.work(N, K - 1, r - 1, c - 2, onboard, cache) + \
                self.work(N, K - 1, r + 2, c + 1, onboard, cache) + \
                self.work(N, K - 1, r + 2, c - 1, onboard, cache) + \
                self.work(N, K - 1, r - 2, c + 1, onboard, cache) + \
                self.work(N, K - 1, r - 2, c - 1, onboard, cache)
            cache[(K, r, c)] = count
            return count
    
    
        def knightProbability(self, N, K, r, c):
            """
            :type N: int
            :type K: int
            :type r: int
            :type c: int
            :rtype: float
            """
            cache = {}
            onboard = self.work(N, K, r, c, 0, cache)
            return onboard / (8 ** K)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.