🦄🌿🤑Pythonic Solution | Video Explanation🔥 | Dynamic Programming | Top Down DP
Intuition\nTo solve this problem efficiently, we can use dynamic programming and memoization to avoid redundant calculations. \n Describe your first thoughts on
# Intuition\nTo solve this problem efficiently, we can use dynamic programming and memoization to avoid redundant calculations. \n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n**Video Description coming soon. Please upvote the post while we work on the video\uD83D\uDE4F\uD83D\uDE4F**\n\n# Time Complexity\n\n- The time complexity of the solution depends on the number of recursive calls and the number of unique subproblems encountered during the recursion. \n\n- is_valid() function: The is_valid() function is called once for each unique position (x, y) on the chessboard. Since the chessboard has dimensions n x n, the function will be called approximately n^2 times. The time complexity of this function is constant, O(1), as it only involves simple arithmetic operations and comparisons.\nsolve() function: The solve() function is a recursive function that explores all possible moves from a given position (x, y) and the given number of remaining moves k. For each position, it explores 8 possible moves. As a result, the number of recursive calls grows exponentially with respect to the number of remaining moves k. At each level of recursion, there are 8 recursive calls. Therefore, the number of recursive calls can be roughly approximated as 8^k.\n\n- Memoization with @cache: The @cache decorator caches the results of previously encountered subproblems, allowing the function to avoid redundant calculations. This effectively reduces the number of recursive calls to unique subproblems. The caching mechanism ensures that each unique subproblem is solved only once, and the result is directly retrieved from the cache during subsequent encounters. As a result, the total number of unique subproblems encountered will be significantly smaller than 8^k.\nConsidering these factors, the overall time complexity of the solution can be expressed as follows:\n\n# O(n^2 * 8^k)\n\n# Space complexity:\n- The space complexity of the solution is determined by the memory used during the recursive calls and the memoization cache. Let\'s analyze it step by step:\n\n- Stack space: During the recursive calls to the solve() function, the Python call stack keeps track of intermediate function calls and their parameters. Since each recursive call requires a constant amount of memory, the maximum depth of the recursion will be equal to the number of remaining moves k. Therefore, the space complexity due to the call stack is O(k).\n\n- Memoization cache: The @cache decorator caches the results of previously encountered subproblems. As a result, it consumes memory to store the cached results. The number of unique subproblems that can be encountered during the recursion is significantly smaller than 8^k, as many subproblems are reused from the cache. Therefore, the space complexity due to the memoization cache can be approximated as O(n^2 * k).\nCombining these factors, the overall space complexity of the solution can be expressed as:\n\n# O(n^2 * k)\n\n- Note: As previously mentioned, the space complexity can be reduced to O(n^2) by using an iterative approach without recursion and memoization. However, the recursive solution with memoization is more intuitive and easier to implement for this problem.\n\n\n# Code\n```\n\nfrom functools import cache\n\nclass Solution:\n    def __init__(self):\n        # Initialize variables to store chessboard size and number of moves\n        self.n = 0\n        self.k = 0\n        # Define the eight possible knight moves as relative coordinates\n        self.states = [(1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2)]\n\n    # Helper function to check if given coordinates (x, y) are within chessboard boundaries\n    @cache\n    def is_valid(self, x, y):\n        if 0 <= x < self.n and 0 <= y < self.n:\n            return True\n        return False\n\n    # Function to calculate the probability of knight staying on the board after k moves\n    @cache\n    def solve(self, x, y, k):\n        # Base case: If k is 0, knight is guaranteed to stay on the board\n        if k == 0:\n            return 1\n        rate = 0\n        # Loop through all eight possible knight moves\n        for dx, dy in self.states:\n            n_x, n_y = x + dx, y + dy\n            # Check if the new coordinates are valid (within chessboard boundaries)\n            if not self.is_valid(n_x, n_y):\n                continue\n            # Calculate the probability for the current move and add it to the rate\n            rate += 0.125 * self.solve(n_x, n_y, k - 1)\n        return rate\n\n    # Main function to solve the knight probability problem\n    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:\n        # Update the chessboard size and number of moves\n        self.n = n\n        self.k = k\n        # Edge case: If k is 0, simply check if the initial position is valid on the board\n        if k == 0:\n            return float(self.is_valid(row, column))\n        # Otherwise, call the solve function with the starting position and k\n        return self.solve(row, column, k)\n\n```
['Dynamic Programming', 'Recursion', 'Python3']