Python🔥Java🔥C++🔥Simple Solution🔥Easy to Understand
!! BIG ANNOUNCEMENT !!\nI am currently Giving away my premium content well-structured assignments and study materials to clear interviews at top companies relat
**!! BIG ANNOUNCEMENT !!**\nI am currently Giving away my premium content well-structured assignments and study materials to clear interviews at top companies related to computer science and data science to my current Subscribers. This is only for first 10,000 Subscribers.  **DON\'T FORGET** to Subscribe\n\n# Search \uD83D\uDC49 `Tech Wired Leetcode` to Subscribe\n\n# or\n\n\n# Click the Link in my Profile\n# Approach:\n\n- If the minimum target points K is 0 or the maximum total points N is greater than or equal to K + W, it is guaranteed to win, so return 1.0.\n- Create a dp array of size N + 1 to store the probabilities. \n- Initialize all elements to 0.0, except dp[0] which is set to 1.0.\n- Initialize windowSum to 1.0 to keep track of the sum of the previous maxPts probabilities.\n- Initialize probability to 0.0 to store the final probability of winning.\n- Iterate from 1 to N and calculate the probabilities using dynamic programming:\n- Update dp[i] as windowSum / maxPts.\n- If i is less than K, add dp[i] to windowSum.\n- If i is greater than or equal to K, add dp[i] to probability.\n- If i - maxPts is greater than or equal to 0, subtract dp[i - maxPts] from windowSum.\n- Return probability as the result.\n# Intuition:\n\n- We can think of the game as a series of draws, where at each draw we can draw any number from 1 to maxPts with equal probability.\n- To calculate the probability of winning, we use dynamic programming to keep track of the probabilities for each point.\n- Starting from point 0, we calculate the probabilities for each subsequent point up to N.\n- At each point i, the probability of reaching that point is the sum of probabilities from the previous maxPts points divided by maxPts.\n- If the current point i is less than K, we add the probability to the windowSum to keep track of the sum of previous probabilities.\n- If the current point i is greater than or equal to K, we add the probability to the probability variable, which represents the final probability of winning.\n- We maintain a sliding window of size maxPts to efficiently calculate the probabilities, removing the probability of the point that falls outside the window and adding the probability of the current point.\n- Finally, we return the probability as the result, which represents the probability of winning the game.\n\n```Python []\nclass Solution:\n    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n        if k == 0 or n >= k + maxPts:\n            return 1.0\n        \n        windowSum = 1.0\n        probability = 0.0\n        \n        dp = [0.0] * (n + 1)\n        dp[0] = 1.0\n        \n        for i in range(1, n + 1):\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:\n                windowSum -= dp[i - maxPts]\n        \n        return probability\n```\n```Java []\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        \n        double windowSum = 1.0;\n        double probability = 0.0;\n        \n        double[] dp = new double[n + 1];\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            \n            if (i >= maxPts) {\n                windowSum -= dp[i - maxPts];\n            }\n        }\n        \n        return probability;\n    }\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    double new21Game(int n, int k, int maxPts) {\n        if (k == 0 || n >= k + maxPts) {\n            return 1.0;\n        }\n        \n        double windowSum = 1.0;\n        double probability = 0.0;\n        \n        vector<double> dp(n + 1, 0.0);\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            \n            if (i >= maxPts) {\n                windowSum -= dp[i - maxPts];\n            }\n        }\n        \n        return probability;\n    }\n};\n\n```\n\n# An Upvote will be encouraging \uD83D\uDC4D
['Dynamic Programming', 'C++', 'Java', 'Python3']