Easy Python BFS like DP, 168ms, super fast without tricks, with detailed explanation.
\nclass Solution(object):\n    def knightProbability(self, N, K, r, c):\n        """\n        :type N: int\n        :type K: int\n        :type r: int\n        
```\nclass Solution(object):\n    def knightProbability(self, N, K, r, c):\n        """\n        :type N: int\n        :type K: int\n        :type r: int\n        :type c: int\n        :rtype: float\n        """\n        # O(K*n^2) worst case, keep adding the probability of getting out of the board.\n        moves = [(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]\n        memo, out_board_p = {(r, c): 1}, 0\n        # for each step we will create a new dict to record the onboard coordinates and their probabilities.\n        for step in range(K):\n            next_memo = collections.defaultdict(int)\n            for (i, j), prob in memo.items():\n                for d in moves:\n                    di, dj = i+d[0], j+d[1]\n                    # if the next step is on the board, we record it for next step\'s calculation\n                    if 0<=di<N and 0<=dj<N:\n                        next_memo[(di,dj)] += prob * 0.125\n                    # if the next step is not on the board, we sum it to our accumulate probability of out-board.\n                    else:\n                        out_board_p += prob * 0.125\n            memo = next_memo\n        # the on-board prob = 1 - the accumulate out board prob\n        return 1-out_board_p\n```
[]