Recursion with memoization TLE, O(n^2), then optimization to iterative sliding window
\nclass Solution:\n    """\n    Recursive solution: Begin with cur_points.\n    If cur_points<k, play next round:\n    For each draw from 1 to maxPts:\n        
```\nclass Solution:\n    """\n    Recursive solution: Begin with cur_points.\n    If cur_points<k, play next round:\n    For each draw from 1 to maxPts:\n        play the next round with draw points. Find the probability of winning from that many points. Divide by maxPts.\n    \n    Add the weighted probabilites together to get final result.\n    \n    Base case is:\n        when cur_points>n, the probabilty is 0\n        elif cur_points>=k, probability is 1.\n        \n    \n    There are multiple ways to reach a new threshold, e.g. for threshold n-2 by drawing 1 twice or by drawing 2 once, so we memoize the solution.\n    """\n    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n        memo=dict()\n        \n        def prob(cur_points): #probability of winning starting from cur_points\n            if cur_points>n:\n                memo[cur_points]=0\n            elif cur_points>=k:\n                memo[cur_points]=1\n            if cur_points in memo:\n                return memo[cur_points]\n            \n            output=0\n            for next_draw in range(1,maxPts+1):\n                next_prob=prob(cur_points+next_draw)\n                output+=next_prob/maxPts\n            \n            memo[cur_points]=output\n            return output\n        \n        return prob(0)\n```\n\n```\nclass Solution:\n    """\n    Recursive solution: O(n*max_pts)\n    Begin with cur_points.\n    If cur_points<k, play next round:\n    For each draw from 1 to maxPts:\n        play the next round with draw points. Find the probability of winning from that many points. Divide by maxPts.\n    \n    Add the weighted probabilites together to get final result.\n    \n    Base case is:\n        when cur_points>n, the probabilty is 0\n        elif cur_points>=k, probability is 1.\n        \n    There are multiple ways to reach a new threshold, e.g. for threshold n-2 by drawing 1 twice or by drawing 2 once, so we memoize the solution.\n    \n    Optmization to iterative solution:\n    let dp[i] be the probability of winning from i points. It is initialized as:\n    \n    dp[i]=1 for i =k,...,n\n    dp[i]=0 for i=n+1,...,k+max_pts-1 (if k+max_pts<=n+1, probability of winning is everywhere 1)\n    0--------k---n---\n    ---------[--max_pts-]\n    \n    we have an expression:\n    dp[k-1]=(n+1-k)/max_pts\n    dp[i-1]=dp[i]+dp[i]/max_pts-dp[i+max_pts+1]/max_pts\n    \n    Alternatively, we can keep track of the current sum of the probabilities cur_sum\n    """\n    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n        if k-1+maxPts<=n:\n            return 1.0\n        \n        dp=[0 for _ in range(k+maxPts)]\n        \n        for i in range(k,n+1):\n            dp[i]=1\n        cur_sum=n-k+1\n        for i in range(k-1,-1,-1):\n            dp[i]=cur_sum/maxPts\n            cur_sum=cur_sum+dp[i]-dp[i+maxPts]\n        return dp[0]\n```
[]