C++ || Bottom Up DP || O(N) || Beats 100%
If points are curr then probability at this stage depends on curr+1,curr+2,....., curr+maxPts.\nProbability for curr will then be the sum of all these elements 
If points are curr then probability at this stage depends on curr+1,curr+2,....., curr+maxPts.\nProbability for curr will then be the sum of all these elements divided my maxPts.\nThe base case will be when points are greater or equal to k, where if points are less than or equal to n then probability at this stage would be 1.\n\nI started with top down DP.\n![WhatsApp Image 2023-05-25 at 13.06.10.jpg](https://assets.leetcode.com/users/images/72a88ff2-8f80-482e-8bdc-af710c970ac9_1685000243.2486289.jpeg)\n(I know the first tree that i should have explored should be 1 then 2 then 3 but it was too long to represent)\n# Code (TopDown - Gives TLE )\n```\nclass Solution {\npublic:\n    double game(int curr,int k,int n,int maxPts,vector<double>&dp){\n        if(curr>=k) return curr<=n;\n        if(dp[curr]!=-1) return dp[curr];\n        double sum = 0;\n        for(int i=1;i<=maxPts;i++){\n            sum+=game(curr+i,k,n,maxPts,dp);\n        }\n        return dp[curr] = sum/maxPts;\n        \n    }\n    double new21Game(int n, int k, int maxPts) {\n        vector<double> dp(n,-1.0);\n        return game(0,k,n,maxPts,dp);\n    }\n};\n```\nThis can be easily converted to Bottom Up. i\'th element depends on the sum of i+1,i+2,...,i+maxPts divided by maxPts. Base case would be similar to TopDown. But it will still give TLE.\nI think the reason is that the summing part takes linear time. If there was some way to make it somehow constant. Then i saw the tag "Sliding window".\nIf we know the sum of a window, we can get sum of next window by subtracting the last element of window and add the new element to it. Time to math.\n![WhatsApp Image 2023-05-25 at 13.22.56.jpg](https://assets.leetcode.com/users/images/131f3ff1-999a-4de4-a635-abf90f51554b_1685001226.2865462.jpeg)\n\nNow we just need to make the initial window and we can apply this relation.\n\n# Code\n```\nclass Solution {\npublic:\n    double new21Game(int n, int k, int maxPts) {\n        if(n==0 || k==0 ) return 1.0;\n        vector<double> dp(k+maxPts+1,0);\n        double sum = 0;\n        //Dealing with base case when points greater than k\n        for(int i=0;i<maxPts;i++){\n            dp[k+i] = (k+i)<=n;\n            //Calculating the initial window\n            sum+=dp[k+i];\n        }\n        //Initial window value\n        dp[k-1] = sum/maxPts;\n\n        //Calculating other probabilities using the relation\n        for(int i=k-2;i>=0;i--){\n            dp[i] = dp[i+1] + ((dp[i+1] - dp[i+maxPts+1])/maxPts);\n        }\n        return dp[0];\n    }\n};\n```\n![WhatsApp Image 2023-05-25 at 12.44.49.jpg](https://assets.leetcode.com/users/images/1868285c-64b3-47a5-a68d-2f879b782546_1685001403.2064579.jpeg)\n\nDo upvote if this solution seemed helpful.
['Math', 'Dynamic Programming', 'Memoization', 'Sliding Window', 'C++']