C++ Dynamic Programming with Sliding window 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    vector<double> d
\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    vector<double> dp(n + 1, 0.0);\n    double winsum=0;\n    \n    for(int i=k;i<k+maxPts;++i){\n        if (i<=n){\n            winsum+=1;\n            dp[i]=1.0;\n        }\n    }\n    for(int i=k-1;i>=0;--i){\n        double remove=0.0;\n        dp[i]=winsum*(1.0/maxPts);\n        if(i+maxPts<=n){\n            remove=dp[i+maxPts];\n        }\n        winsum+=dp[i]-remove;\n    }\n    return dp[0];\n    }\n};\n```
['Dynamic Programming', 'Sliding Window', 'C++']