Python | DP | Explained
The solution:\n\nclass Solution:\n    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n        if k == 0:\n            return 1\n        dp = [1] + [
**The solution**:\n```\nclass Solution:\n    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n        if k == 0:\n            return 1\n        dp = [1] + [0] * n\n        s = 1\n        for i in range(1, n + 1):\n            if i - maxPts >= k:\n                break\n            dp[i] = s / maxPts\n            if i - maxPts >= 0:\n                s -= dp[i - maxPts]\n            if i < k:\n                s += dp[i]\n        return sum(dp[k:])\n```\n\n**Explanation:**\nThe given solution uses dynamic programming to calculate the probability that Alice has n or fewer points in the game. Let\'s break down the logic step by step:\n\n1. Initialize the probability array `dp` with `dp[0] = 1` (Alice starts with 0 points) and all other elements as 0. This array will store the probabilities of having a certain number of points.\n\n2. Initialize the sum variable `s` to 1. `s` represents the cumulative probability of reaching the current point.\n\n3. Iterate over the range from 1 to n+1 (inclusive) to calculate the probabilities for each possible point value.\n\n4. Check if the current point value minus the maximum points `maxPts` is greater than or equal to k. If so, break the loop because Alice can already achieve k or more points, and there is no need to calculate further.\n\n5. Calculate the probability `dp[i]` for the current point value. It is the sum of the probabilities of reaching the previous `maxPts` points, divided by `maxPts` (since each draw has equal probabilities).\n\n6. If the current point value minus `maxPts` is greater than or equal to 0, subtract the probability `dp[i - maxPts]` from the sum `s`. This step ensures that the sum `s` only contains the probabilities of the last `maxPts` points.\n\n7. If the current point value is less than k, add the probability `dp[i]` to the sum `s`. This step updates the cumulative probability `s` with the current point\'s probability.\n\n8. After the loop, return the sum of probabilities from index k to the end of the `dp` array. This represents the probability that Alice has n or fewer points.\n\nThe time complexity of this solution is O(n) because we iterate over the range from 1 to n+1. The space complexity is also O(n) because we use the `dp` array to store the probabilities of each point value.
['Dynamic Programming', 'Python']