Java Solution | Memoization->Bottom Up->Optimization | 3 step optimization for acceptance | 3 ms
Approach\nFor complete acceptance of the solution 3 step process is given below where first we make a recusion along with memoization(gives TLE) then optimising
# Approach\nFor complete acceptance of the solution 3 step process is given below where first we make a recusion along with memoization(gives TLE) then optimising it further using bottom-up iterative approach(gives TLE) then finally applying sliding window in iterative code for most optimized solution!\n\n# Code \nStep 1:\n```\nclass Solution {\n    public double new21Game(int n, int k, int maxPts) {\n        if(k==0 || n>=k-1+maxPts) return 1.0;\n        dp=new Double[n+maxPts+1];\n        double prob=(double)1/(double)maxPts; //probability of occurence of each number between [1, maxPts]\n        return util(n, k, prob, 0, maxPts);\n    }\n    private Double dp[];\n    private double util(int n, int k, double prob, int cur, int max) {\n        if(cur>n) {\n            return 0.0;\n        }\n        if(cur>=k) {\n            return 1.0;\n        } \n        if(dp[cur]!=null) return dp[cur];\n        double sum=0.0;\n        for(int i=1;i<=max;i++) {\n            double ret=util(n, k, prob, cur+i, max);\n            sum+=(prob * ret);\n        }\n        return dp[cur]=sum;\n    }\n}\n```\n\nStep 2:\n```\nclass Solution {\n    public double new21Game(int n, int k, int maxPts) {\n        if(k==0 || n>=k-1+maxPts) return 1.0;\n        double dp[]=new double[n+1];\n        double prob=(double)1/(double)maxPts;\n        for(int i=n;i>0;i--) {\n            if(i>=k) {\n                dp[i]=1.0;\n            }\n            for(int j=1;j<=maxPts;j++) {\n                if(i-j>=0) {\n                    dp[i-j]+=prob*dp[i];\n                }\n            }\n        }\n        return dp[0];\n    }\n}\n```\n\nStep 3:\n```\nclass Solution {\n    public double new21Game(int n, int k, int maxPts) {\n        if(k==0 || n>=k+maxPts-1) return 1.0;\n        double dp[]=new double[n+maxPts];\n        double prob=(double)1/(double)maxPts;\n        double sum=0.0;\n        int j=k-1+maxPts;\n        for(int i=n;i>=0;i--) {\n            if(i>=k) {\n                dp[i]=1.0;\n            }\n            else {\n                dp[i]+=prob*sum;\n                if(j-i==maxPts) {\n                    sum-=dp[j--];\n                }\n            }\n            sum+=dp[i];\n        }\n        return dp[0];\n    }\n}\n```\n\n
['Dynamic Programming', 'Memoization', 'Sliding Window', 'Probability and Statistics', 'Java']