DP and Probability || Explaination || ✔
-> Solution is inspired from https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP-O(N) and https://leetcode.com/problems/new-21-game/discuss/228
-> Solution is inspired from https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP-O(N) and https://leetcode.com/problems/new-21-game/discuss/228406/Logical-Thinkingsolution \n```\nclass Solution {\n   \npublic:\n    double new21Game(int n, int k, int maxPts) {\n        if(n >= k+maxPts || k == 0)return 1;\n        vector<double>dp(n+1);\n        dp[0] = 1.0;\n        double ans = 0,window_sum = 1;\n        // prob(i) = prob(i-maxpts)*1/maxpts + prob(i-maxpts+1)*1/(maxpts+1) + ...\n        // since we can only draw a number from 1 to maxpts so to get i points we first reach i-maxpts or i-maxpts+1 or ...\n        // after that we draw some number between 1 to maxpts which would have prob of 1/maxpts \n        // now this formula can be tranformed into a formula with sum as\n        // prob(i) = (prob(i-maxpts)+prob(i-maxpts+1)+...)/maxpts\n        // so we can maintain probabilty sum of the window and start adding probabilty for number between k and n as \n        // probabilty of numbers less than k can only be used for window_sum and we will not be adding probability of \n        // points that are greater than equal to k as we would stop there we would only be adding their probabily using \n        // the probability of all points less than i and inside the window of maxpts\n        for(int i = 1; i<=n;i++){\n            dp[i] =  (window_sum/(double)maxPts);\n            if(i < k)window_sum+=dp[i];\n            else ans += dp[i];\n            if(i >= maxPts)window_sum -= dp[i-maxPts];\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming']