[Python] 4 solutions with DFS, BFS, DP and space optimized DP
\nfrom collections import deque\nclass Solution(object):\n    def knightProbability(self, N, K, r, c):\n        """\n        :type N: int\n        :type K: int\
```\nfrom collections import deque\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        # DFS\n        mem = [[[-1] * N for _ in range(N)] for _ in range(K + 1)]\n        offsets = [[-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2]]\n        \n        def helper(i, j, k):\n            if k == 0:\n                mem[k][i][j] = 1\n                return mem[k][i][j]\n            if mem[k][i][j] != -1:\n                return mem[k][i][j]\n            \n            rst = 0\n            for off in range(8):\n                next_i, next_j = i + offsets[off][0], j + offsets[off][1]\n                if 0 <= next_i < N and 0 <= next_j < N:\n                    rst += 0.125 * helper(next_i, next_j, k - 1)\n            mem[k][i][j] = rst\n            return mem[k][i][j]\n            \n        return helper(r, c, K)\n        \n        # BFS\n        if K == 0:\n            return 1\n        \n        dp = [[[0] * N for _ in range(N)] for _ in range(K + 1)]\n        offsets = [[-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2]]\n        dp[0][r][c], k, q = 1, 1, deque([(r, c)]) \n        \n        while q and k <= K:\n            rst, seen = 0, set()\n            for _ in range(len(q)):\n                i, j = q.popleft()\n                prev_prob = dp[k - 1][i][j]\n                for off in range(8):\n                    cur_i, cur_j = i + offsets[off][0], j + offsets[off][1]\n                    if 0 <= cur_i < N and 0 <= cur_j < N:\n                        dp[k][cur_i][cur_j] +=  prev_prob * 0.125\n                        rst += prev_prob * 0.125\n                        if cur_i * N + cur_j not in seen:\n                            q.append((cur_i, cur_j))\n                            seen.add(cur_i * N + cur_j)\n            k += 1\n        return rst                        \n        \n        # DP\n        dp = [[[0] * N for _ in range(N)] for _ in range(K + 1)]\n        dp[0][r][c] = 1\n        offsets = [[-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2]]\n        \n        for k in range(1, K + 1):\n            for i in range(N):\n                for j in range(N):\n                    for off in range(8):\n                        prev_i, prev_j = i + offsets[off][0], j + offsets[off][1]\n                        if 0 <= prev_i < N and 0 <= prev_j < N:\n                            dp[k][i][j] += 0.125 * dp[k - 1][prev_i][prev_j]\n        return sum([sum(row) for row in dp[K]])\n```\n\nOptimized the DP space from `O(K * N * N)` to `O(2 * N * N)`:\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        # dp[k][i][j]: at step k, probability of cell[i][j] being visited\n        dp = [[[0] * N for __ in xrange(N)] for _ in xrange(2)]\n        offsets = [[-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2]]\n        dp[0][r][c] = 1\n        for k in xrange(1, K + 1):\n            dp[k % 2] = [[0] * N for _ in xrange(N)]\n            for i in xrange(N):\n                for j in xrange(N):\n                    if dp[(k - 1) % 2][i][j] != 0:\n                        for off in offsets:\n                            if 0 <= i + off[0] < N and 0 <= j + off[1] < N:\n                                dp[k % 2][i + off[0]][j + off[1]] += dp[(k - 1) % 2][i][j] / 8.0\n        return sum([sum(row) for row in dp[K % 2]])\n```
[]