👨‍💻 Easy Approach | C++ | O(N)
Intuition\n Describe your first thoughts on how to solve this problem. \nTo solve the problem, we can use dynamic programming to calculate the probability that 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve the problem, we can use dynamic programming to calculate the probability that Alice has n or fewer points. We can define a dynamic programming array dp of size n + 1, where dp[i] represents the probability of having i or fewer points.\n\nWe can initialize dp[0] to 1, as Alice starts with 0 points. Then we can iterate from 1 to n and calculate dp[i] based on the previous probabilities.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Create a dynamic programming array dp of size n + 1 to store the probabilities.\n- Initialize dp[0] to 1, as Alice starts with 0 points.\n- Initialize probability variable to 0 to keep track of the total probability of having n or fewer points.\n- Initialize point variable to 1, as the probability of starting with 0 points is 1.\n- Iterate from 1 to n and calculate dp[i] based on the previous probabilities:\n- Set dp[i] to point / maxPts, as the probability of gaining i points is equal to the probability of gaining i-1 points divided by maxPts.\n- If i is less than k, add dp[i] to point to keep track of the total probability of having less than k points.\n- If i is greater than or equal to k, add dp[i] to probability to keep track of the total probability of having k or fewer points.\n- If i - maxPts is greater than or equal to 0, subtract dp[i - maxPts] from point to account for the points that can no longer be obtained.\n- Return probability, which represents the probability that Alice has n or fewer points.\n\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    double new21Game(int n, int k, int maxPts) {\n        if (k == 0 || n >= k + maxPts)\n            return 1.0;\n        vector<double> dp(n + 1);\n        double point = 1.0, probability = 0.0;\n        dp[0] = 1.0;\n        for (int i = 1; i <= n; i++) {\n            dp[i] = point / maxPts;\n            if (i < k)\n                point += dp[i];\n            else\n                probability += dp[i];\n            if (i - maxPts >= 0)\n                point -= dp[i - maxPts];\n        }\n        return probability;\n    }\n};\n```\n\n# An Upvote will be encouraging \uD83D\uDC4D\n
['Dynamic Programming', 'C++']