Java Solution for New 21 Game Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to calculate the probability that Alice has n or fewer points. To achieve t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to calculate the probability that Alice has n or fewer points. To achieve this, we can consider the probability at each point and use dynamic programming to build up the probabilities iteratively.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. First, we handle the base cases. If k is 0 or if n is greater than or equal to k + maxPts, Alice will always stop drawing after the first round and have a probability of 1.0 to have n or fewer points.\n1. We create an array dp to store the probabilities for each possible number of points.\n1. Initialize dp[0] to 1.0, indicating that Alice starts with 0 points.\n1. We use a sliding window approach to calculate the probabilities iteratively. We maintain a windowSum variable that represents the sum of probabilities within the window of size maxPts.\n1. Iterate from 1 to n and calculate dp[i] as windowSum / maxPts since each draw has equal probabilities.\n1. If i is less than k, we update windowSum by adding dp[i] since we can continue drawing.\n1. Otherwise, if i is greater than or equal to k, we update probability by adding dp[i] since Alice has stopped drawing at this point.\n1. We adjust the windowSum by subtracting the probability that falls outside the window, i.e., dp[i - maxPts], if it exists.\n1. Finally, we return the calculated probability.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of the solution is O(n) because we iterate from 1 to n to calculate the probabilities.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(n) because we use an array dp of size n+1 to store the probabilities.\n\n# Code\n```\nclass Solution {\n    public double new21Game(int n, int k, int maxPts) {\n        if (k == 0 || n >= k + maxPts)\n        return 1.0;\n    \n    double[] dp = new double[n + 1];\n    double windowSum = 1.0;\n    double probability = 0.0;\n    \n    dp[0] = 1.0;\n    \n    for (int i = 1; i <= n; i++) {\n        dp[i] = windowSum / maxPts;\n        \n        if (i < k)\n            windowSum += dp[i];\n        else\n            probability += dp[i];\n        \n        if (i - maxPts >= 0)\n            windowSum -= dp[i - maxPts];\n    }\n    \n    return probability;\n    }\n}\n```
['Java']