Naive DFS to Sliding Window step by step intuitive conversion giving O(k+m) TC
This problem can be naively solved using a DFS DP solution:\n\nclass Solution:\n    def new21Game(self, n: int, k: int, m: int) -> float:\n        @cache\n     
This problem can be naively solved using a DFS DP solution:\n```\nclass Solution:\n    def new21Game(self, n: int, k: int, m: int) -> float:\n        @cache\n        def f(p):\n            if p >= k:\n                return 1 if p <= n else 0\n            return sum(f(p+i) for i in range(1, m+1))/m\n        return f(0)\n```\nIt can then be converted into a DP array solution:\n```\nclass Solution:\n    def new21Game(self, n: int, k: int, m: int) -> float:\n        dp = [1]*(k+m)\n        for i in range(k+m-1, n, -1):\n            dp[i] = 0\n        for i in range(k-1, -1, -1):\n            dp[i] = sum(dp[i+1:i+m+1])/m\n        return dp[0]\n```\nWe can now see there is opportunity to optimise our solution using the Sliding Window pattern:\n```\nclass Solution:\n    def new21Game(self, n: int, k: int, m: int) -> float:\n        dp = [1]*(k+m)\n        for i in range(k+m-1, n, -1):\n            dp[i] = 0\n        x = sum(dp[k:k+m])\n        for i in range(k-1, -1, -1):\n            dp[i] = x/m\n            x += dp[i] - dp[i+m]\n        return dp[0]\n```\nTime complexity: worst case: $$O(k+m)$$\nSpace complexity: $$O(k+m)$$
['Python3']