Fast C++ O(n) solution
Intuition\n Describe your first thoughts on how to solve this problem. \nMy first thought was to use dynamic programming to approach this problem. \n# Approach\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMy first thought was to use dynamic programming to approach this problem. \n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can use an array of doubles, dp, to store the probability that we reach each score. We can start with dp[0] = 1.0, indicating that the probability of reaching the score 0 is 1.0. For all the scores between 0 and k, we can use the probability of reaching any score i-j, where j is the points we get on the turn (j <= maxPts), to calculate the probability of reaching score i using dynamic programming.\n\nWe can also use a sliding window technique to keep track of the cumulative probability of reaching scores between i and i - maxPts. We can add the probability of reaching the current score to this window and subtract the probability of reaching the score i - maxPts from the window. This will help us to keep track of the cumulative probability of reaching scores between i and i - maxPts.\n\nFinally, for all the scores between k and n, we can calculate the probability of reaching this score by adding the probability of reaching any score i-j, where j is the points we get on the turn (j <= maxPts). The sum of all these probabilities will be the final answer.\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of this solution is O(n), where n is the target score. This is because we iterate over all the scores between 0 and n and calculate the probability of reaching each score.\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity of this solution is O(n), where n is the target score. This is because we use an array of size n to store the probability of reaching each score.\n# Code\n```\nclass Solution {\npublic:\n    double new21Game(int n, int k, int maxPts) {\n        if (k == 0 || n >= k + maxPts - 1) return 1.0;\n        vector<double> dp(n + 1);\n        dp[0] = 1.0;\n        double W = 1.0, res = 0.0;\n        for (int i = 1; i <= n; ++i) {\n            dp[i] = W / maxPts;\n            if (i < k) W += dp[i];\n            else res += dp[i];\n            if (i - maxPts >= 0) W -= dp[i - maxPts];\n        }\n        return res;\n    }\n};\n```
['C++']