Simple C++ solution using DP (tabulation) method
Intuition\nThe intuition behind this solution is to use dynamic programming to calculate the probabilities of achieving different scores in the New 21 Game. The
# Intuition\nThe intuition behind this solution is to use dynamic programming to calculate the probabilities of achieving different scores in the New 21 Game. The algorithm iteratively calculates the probabilities and keeps track of the cumulative sum.\n\n# Approach\n- The game has three parameters: \'n\' represents the maximum total points that can be obtained, \'k\' is the target score to reach or exceed, and \'maxPts\' is the maximum number of points that can be drawn in a single turn.\n\n- If \'k\' is zero or if \'n\' is greater than or equal to \'k + maxPts\', it means we can achieve the target score \'k\' or higher with certainty. In this case, we return 1.0, indicating a 100% chance of winning.\n\n- We create a dynamic programming array \'dp\' of size \'n + 1\'. Each element \'dp[i]\' represents the probability of getting \'i\' points.\n\n- We initialize \'currSum\' to 1.0, representing the probability of starting with 0 points. \'ans\' is initialized to 0.0, which will store the final answer.\n\n- We set \'dp[0]\' to 1.0 because the probability of starting with 0 points is 100%.\n\n- We iterate from 1 to \'n\' and calculate the probability for each \'i\':\n\n    a. \'dp[i]\' is set to \'currSum\' divided by \'maxPts\'. This represents the probability of getting \'i\' points in the current turn.\n\n    b. If \'i\' is less than \'k\', we update \'currSum\' by adding \'dp[i]\'. This accounts for the current turn\'s points and adds it to the cumulative sum.\n\n    c. If \'i\' is greater than or equal to \'k\', we add \'dp[i]\' to \'ans\'. This keeps track of the probability of achieving \'k\' or more points.\n\n    d. If the index \'i - maxPts\' is greater than or equal to 0, it means that the \'maxPts\' points drawn \'maxPts\' turns ago are no longer in play. So, we subtract \'dp[i - maxPts]\' from \'currSum\' to update the cumulative sum accordingly.\n\n- After the iteration, \'ans\' will contain the probability of reaching or exceeding the target score \'k\' with the given constraints.\n\n- Finally, we return \'ans\', which represents the probability of winning the New 21 Game.\n\n# Complexity\n- Time complexity:\nThe time complexity of this solution is O(n), where n is the maximum total points that can be obtained.\n\n- Space complexity:\nThe space complexity of this solution is O(n).\ndyn\n\n![upvote.png](https://assets.leetcode.com/users/images/a0c67592-a276-4863-9d58-73609aa5d414_1684996807.9494553.png)\n\n\n# Code\n```\nclass Solution {\npublic:\n    double new21Game(int n, int k, int maxPts) {\n\n           if (k == 0 || n >= k + maxPts) {\n            return 1.0;\n        }\n        vector<double> dp(n + 1);\n        double currSum = 1.0;\n        double ans = 0.0;\n\n         dp[0] = 1.0;\n\n        for (int i = 1; i < n+1; i++) {\n\n            dp[i] = currSum / maxPts;\n\n            if (i < k) \n                currSum += dp[i];\n\n             else \n                ans += dp[i];\n            \n            if (i - maxPts >= 0) \n                currSum -= dp[i - maxPts];\n            \n        }\n\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C++']