[Simple] Beat 100% + explanation
\n\nclass Solution:\n    # In each draw, prob is based on last maxPts draws\n    # So we can use a sliding window starting at 1..=maxPts\n    def new21Game(self
![Screen Shot 2023-07-28 at 16.33.58.png](https://assets.leetcode.com/users/images/dac33723-4834-4224-8b53-7ca6f998b3ea_1690576788.6828115.png)\n```\nclass Solution:\n    # In each draw, prob is based on last maxPts draws\n    # So we can use a sliding window starting at 1..=maxPts\n    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n        if not k:\n            return 1\n\n        # dp[i] = probability of getting i points at any point in the game\n        dp = [0.0] * (n+1)\n        dp[0] = 1\n\n        # cumulative probability of all states that can reach i \u2014 starts at 1 bc dp[0]=1\n        # represents the sum of a sliding window\n        prob_of_previous_states = 1\n\n        for i in range(1, n+1):\n            # prob of drawing num = sum_allprevs(prob of reaching prev state + 1/maxpts)\n            # = prob of all prev states * 1/maxPts\n            dp[i] = prob_of_previous_states / maxPts\n\n            # if A continues drawing, we add the current entry to the cumulative sum\n            if i < k:\n                prob_of_previous_states += dp[i]\n\n            # If A continues drawing, we subtract the out of range entry from the cumulative sum\n            # This is because that entry cannot reach the next value\n            if 0 <= i - maxPts < k:\n                prob_of_previous_states -= dp[i - maxPts]\n\n\n        # we want the probability that the final score is n or fewer\n        # because she stops drawing at k, this is equivalent to the probability that the final score is in [k, n]\n        # in other words, we want sum(dp[i]) | k \u2264 i \u2264 n\n        # dp is already upper bounded by n, so sum(dp[k:]) is our answer\n        return sum(dp[k:])\n```\n
['Dynamic Programming', 'Sliding Window', 'Python3']