Python Elegant & Short | Top-Down DP | Memoization
Complexity\n- Time complexity: O(n^{2}k)\n- Space complexity: O(n^{2}k)\n\n# Code\n\nclass Solution:\n    MOVES = (\n        (1, 2), (1, -2),\n        (2, 1), (
# Complexity\n- Time complexity: $$O(n^{2}*k)$$\n- Space complexity: $$O(n^{2}*k)$$\n\n# Code\n```\nclass Solution:\n    MOVES = (\n        (1, 2), (1, -2),\n        (2, 1), (2, -1),\n        (-1, 2), (-1, -2),\n        (-2, 1), (-2, -1),\n    )\n\n    def knightProbability(self, n: int, moves: int, start_row: int, start_col: int) -> float:\n        @cache\n        def dp(i: int, j: int, k: int) -> float:\n            if not (0 <= i < n) or not (0 <= j < n):\n                return 0.0\n            if k <= 0:\n                return (1 / len(self.MOVES)) ** moves\n            return sum(dp(i + di, j + dj, k - 1) for di, dj in self.MOVES)\n\n        return dp(start_col, start_row, moves)\n\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Python', 'Python3']