DP of O(n)
Intuition\nUsing probability and sliding window with DP\n\n# Approach\nWithin code\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# C
# Intuition\nUsing probability and sliding window with DP\n\n# Approach\nWithin code\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    double new21Game(int N, int K, int maxPts) {\n        // Corner cases\n        if (K == 0) return 1.0;\n        if (N >= K-1 + maxPts) return 1.0;\n\n        // dp[i] is the probability of getting point i.\n        vector<double> dp(N + 1, 0.0);\n\n        double probability = 0.0; // dp of N or less points.\n        double windowSum = 1.0; // Sliding required window sum\n        dp[0] = 1.0;\n        for (int i = 1; i <= N; i++) {\n            dp[i] = windowSum / maxPts;\n            //probability of getting ith point is more than i/max as we have more than on draws to get points and we are taking sum of all the previous probabilities to add as the new chances then dibide total by max\n\n            if(i < K) windowSum += dp[i];\n            else probability += dp[i];\n            \n            if(i >= maxPts) windowSum -= dp[i - maxPts];\n        }\n\n        return probability;\n    }\n};\n```
['Dynamic Programming', 'Sliding Window', 'Probability and Statistics', 'C++']