C++ Brute and Optimal Approaches
Approach 1: TLE but is useful to understand the intuition\n\n// basically we ll have to find the probability of alice getting\n// a number between [k...n]. beca
Approach 1: TLE but is useful to understand the intuition\n```\n// basically we ll have to find the probability of alice getting\n// a number between [k...n]. because we dont stop drawing until we reach k\n\n// current_prob[i]->denotes the probability of reaching the number i\n\n//note that 2 events are occuring together\n//1. probability of reaching i-1\n//2. probability of picking 1\n// current_prob[i]=current_prob[i-1].P(1) + current_prob[i-2].P(2) + current_prob[i-3].P(3)\n//                     +......+current_prob[i-maxPts].P(maxPts)\n    \n// P(1)=(1/maxPts)\n// P(2)=1/maxPts\n\n// current_prob[i]=current_prob[i-1].(1/maxPts) + current_prob[i-2].(1/maxPts) + current_prob[i-3].(1/maxPts)\n//                     +......+current_prob[i-maxPts].(1/maxPts)\n    \n// max range of the solution:\n// k->k-1+maxPts\n// we cannot consider a number which is greater than the threshold: i-j>k\n// Example:\n// n=21\n// k=18\n// current_prob[21]=(current_prob[20]+current_prob[19]+current_prob[18])X + current_prob[17]\n\nclass Solution {\npublic:\n    double new21Game(int n, int k, int maxPts) {\n        if(k==0)\n            return 1.0;\n        int maxRange=k-1+maxPts;\n        vector<double>current_prob(maxRange+1,0);\n        current_prob[0]=1.0;\n        for(int i=1;i<=maxRange;i++){\n            for(int j=0;j<=maxPts;j++){\n                if(i-j>=0 && i-j<k){\n                    current_prob[i]+=current_prob[i-j]/(double)maxPts;\n                }\n            }\n        }\n        double ans=0;\n        for(int i=k;i<=n;i++){\n            ans+=current_prob[i];\n        }\n        return ans;\n    }\n};\n```\n2. Optimised Code Using Sliding Window\n```C++\n// optimised idea:\n// dp[14]=c.(dp[13]+dp[12]+......+dp[8])\n// dp[15]=c.(dp[14]+dp[13]+......+dp[9])\n\n//sliding window\n\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        int maxRange=k-1+maxPts;\n        vector<double>current_prob(maxRange+1,0);\n        current_prob[0]=1.0;\n        double runningsum=current_prob[0];\n        double result=0.0;\n        for(int i=1;i<=n;i++){\n            current_prob[i]=runningsum/(double)maxPts;\n            \n            //handle the front end of the running sum\n            if(i<k){\n                runningsum+=current_prob[i];\n            }\n            else\n                result+=current_prob[i];\n            //tail end of the running sum\n            if(i-maxPts>=0){\n                runningsum-=current_prob[i-maxPts];\n            }\n        }\n        \n        return result;\n    }\n};\n```
[]