Diagram & Image Explaination🥇 C++ Full Optimized🔥 DP | Well Explained
Diagram\n Describe your first thoughts on how to solve this problem. \n\n\n# Approach\n Describe your approach to solving the problem. \nCheck if Alice can alwa
# Diagram\n<!-- Describe your first thoughts on how to solve this problem. -->\n![code2flow_4fd67K (4).png](https://assets.leetcode.com/users/images/81ac4f36-2325-4a84-94df-525c356d3781_1684973082.8253682.png)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCheck if Alice can always get k or more points. If so, return 1.0.\n\nCreate a vector dp of size n + 1 to store the probabilities of getting each point from 0 to n. Initialize dp[0] = 1.0.\n\nInitialize two variables, sum and res, to keep track of the sum of probabilities and the final result, respectively. Set sum = 1.0.\n\nLoop over all possible points from 1 to n. For each point i, calculate the probability of getting that point by taking the sum of the probabilities of getting the previous maxPts points and dividing by maxPts.\n\nIf i < k, add the probability of getting i points to sum.\n\nIf i >= k, add the probability of getting i points to res.\n\nUpdate sum by subtracting the probability of getting the point i - maxPts.\n\nReturn the value of res, which represents the probability of getting n or fewer points in the game.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n * maxPts) \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n O(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        }\n        vector<double> dp(n + 1);\n        dp[0] = 1.0;\n        double sum = 1.0, res = 0.0;\n        for (int i = 1; i <= n; i++) {\n            dp[i] = sum / maxPts;\n            if (i < k) {\n                sum += dp[i];\n            } else {\n                res += dp[i];\n            }\n            if (i >= maxPts) {\n                sum -= dp[i - maxPts];\n            }\n        }\n        return res;\n    }\n};\n\n```\n![7abc56.jpg](https://assets.leetcode.com/users/images/a2ba280b-03d2-46b8-963d-bef92d7692fa_1684973263.9929566.jpeg)\n
['Dynamic Programming', 'Sliding Window', 'C++', 'Java', 'Python3']