✔️ [Python3] DFS with DP, beats 99% ٩(๑･ิᴗ･ิ)۶٩(･ิᴗ･ิ๑)۶, Explained
UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.\n\nThe probability of the chance to stay on the board after k m
**UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.**\n\nThe probability of the chance to stay on the board after `k` moves are equal to the number of all desired positions at the end divided by all possible outcomes. \n\nAll possible outcomes can be found with the formula `8^k`. Why is that? Because on every step, we always have 8 possible moves (including those that lead out of the board). That means after 2 moves, we can have 8 * 8 possible positions and so on. So the number of positions where we can end up after `k` moves equals the `8^k`. \n\nThe number of desirable outcomes (those that keep us on the board) is what we need to calculate iteratively using Depth-First Search. For that, we must precalculate all possible moves from a particular position on the board. And this gives us some kind of adjacency list. \n\nSince the number of positions on the next moves grows geometrically, there are high chances for overlapping tasks, i.e. when on the same move, we start from the same place multiple times. Thus we need a cache of the result of the recursive function for DFS traversing.\n\nTime: **O(n * n * k)**\nSpace: **O(n * n * k)**\n\nRuntime: 171 ms, faster than **99.87%** of Python3 online submissions for Knight Probability in Chessboard.\nMemory Usage: 23.6 MB, less than **25.13%** of Python3 online submissions for Knight Probability in Chessboard.\n\n```\nclass Solution:\n    def knightProbability(self, n: int, k: int, row0: int, col0: int) -> float:\n\t\n\t\t# precalculate possible moves\n        adj_list = defaultdict(list)\n        d = ((-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2))\n        for row in range(n):\n            for col in range(n):\n                for dx, dy in d:\n                    pos = (row + dx, col + dy)\n                    if 0 <= pos[0] < n and 0 <= pos[1] < n:\n                        adj_list[(row, col)].append(pos)\n\n        @cache\n        def get_leafs_num(pos, h):\n            if h == k:\n                return 1\n            \n            res = 0\n            for next_pos in adj_list[pos]:\n                res += get_leafs_num(next_pos, h + 1)\n                \n            return res            \n            \n        leafs_num = get_leafs_num((row0, col0), 0)\n\n        return leafs_num / 8**k\n```\n\n**UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.**
['Dynamic Programming', 'Python3']