Python Recursive DP Solution with Explanation
Define dp(r, c, k) as the probability that the knight on (r, c) remains on the board after k moves.\nWe\'ll get the recursion below:\ndp(r, c, k) = sum_for_allo
Define `dp(r, c, k)` as the probability that the knight on `(r, c)` remains on the board after `k` moves.\nWe\'ll get the recursion below:\n`dp(r, c, k) = sum_for_allowed_moves(dp(r_new, c_new, k - 1)) / 8`\n\n```\nfrom functools import lru_cache\n\n\nclass Solution:\n    def knightProbability(self, N: int, K: int, r: int, c: int) -> float:\n        @lru_cache(None)\n        def dp(r, c, k):\n            if r < 0 or r >= N or c < 0 or c >= N:\n                return 0\n            elif k <= 0:\n                return 1\n            res = 0\n            for a, b in [(2, 1), (-2, -1), (2, -1), (-2, 1)]:\n                res += dp(r + a, c + b, k - 1)\n                res += dp(r + b, c + a, k - 1)\n            return res / 8\n        \n        return dp(r, c, K)\n```
['Dynamic Programming', 'Python', 'Python3']