Python3 code with 100 percentile, DFS and memoization
I have used recursive DFS with memoization to find the probabilities. But the idea here is to reduce the amount of repetitive computations. Since we have a squa
I have used recursive DFS with memoization to find the probabilities. But the idea here is to reduce the amount of repetitive computations. Since we have a square board (duh, like any other chess board), we can bring down the number of recursive calls significantly. Each square is equivalent to at most 7 other squares (For any square ```(r, c)```, the equivalent squares are ```(c, r)```, ```(r, N - 1 - c)```, ```(c, N - 1 - r)```, ```(N - 1 - r, c)```, ```(N - 1 - c, r)```, ```(N - r - 1, N - c - 1)```, ```(N - c - 1, N - r - 1)```). We can use this to our advantage and store the probabability values for such squares for a given K.\n\n```\nclass Solution:\n    def knightProbability(self, N, K, r, c):        \n        pr = [[[0] * K for j in range(N)] for i in range(N)]\n        def probab(N, K, r, c):\n            if K == 0:\n                return 1\n            elif pr[r][c][K - 1] > 0:\n                return pr[r][c][K - 1]\n            p = 0\n            for move in [[1, 2], [2, 1], [-1, 2], [-2, 1], [-1, -2], [-2, -1], [1, -2], [2, -1]]:\n                rr, cc = r + move[0], c + move[1]\n                if -1 < rr < N and -1 < cc < N:\n                    p += 0.125 * probab(N, K - 1, rr, cc)\n            pr[r][c][K - 1], pr[c][r][K - 1] = p, p\n            pr[r][N - 1 - c][K - 1], pr[c][N - 1 - r][K - 1] = p, p\n            pr[N - 1 - r][c][K - 1], pr[N - 1 - c][r][K - 1] = p, p\n            pr[N - r - 1][N - c - 1][K - 1], pr[N - c - 1][N - r - 1][K - 1] = p, p\n            return p\n        p = probab(N, K, r, c)\n        return p\n```
[]