Java very easy solution
Intuition\n Describe your first thoughts on how to solve this problem. \n- First of all what is this :P. First find the person who created this question and giv
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- First of all what is this :P. First find the person who created this question and give my blessings also.\n- We will solve this problem using dp\n- The questions says alice has to start from 0 points and she can pick any points from 1 to W.\n- If the score ie points sum exceed k she has to stop picking coins.\n- Now we have to return probabilty for the score<=n.\n- Max score she can reach is k-1 + W\n- Suppose she is at k-1 score if she picks 1 point she will reach k and she cannot pick anymore. if she picks W point she will reach k-1 + W and she cannot pick anymore.\n- Input: `n = 21`, `k = 17`, `maxPts = 10`\n- `d[21]` is the probality to reach `21` score.\n- we can reach `d[21]` from `d[11]` by picking max point `10`.\n- It covers cond `i-W>=0` and make our calculation easier\n- `d[21] = d[20]*p(1) + d[19]*p(2) + d[18]*p(3) +.. +d[11]*p(10)`\n- since all have equal probability\n- `d[21] = d[20]*1/W + d[19]*1/W +.. +d[11]*1/W`\n- `d[21] = 1/W*(d[20]+ d[19]+.. +d[11])`\n- Now alice is not allowed to pick points above score k\n- so we will remove `dp[17] to dp[20]`\n- this covers cond `i<k`\n- so our result will be `d[21] = 1/W*(d[16]+ d[15]+.. +d[11])`\n- till k-1 alice has the option to pick points so we will build our sum but from k or above alice cannot pick anymore points and we will remove extra sum.\n- `c = 1/W`\n- `D[16] start = c * (D[6] + D[7] +..+D[15]) = c*D[15]`\n-  `D[16] end = c * (D[7]+ D[8]+..+D[15]) = c*(D[15]-D[6])`\n- `D[17] start = c * (D[7] +D[8]+..+D[16]) = c*D[16]`\n-  `D[17] end = c * (D[8]+D[9]+..+D[16]) = c*(D[16]-D[7])`\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public double new21Game(int n, int k, int W) {\n        \n        if(k==0 || n>=k+W)\n            return 1;\n        double dp[] = new double[n+1], Wsum=1, res=0;\n        dp[0] = 1;\n        for(int i=1; i<=n; i++) {\n            dp[i] = Wsum/W;\n            if(i<k)\n                Wsum += dp[i];\n            else\n                res += dp[i];\n            \n            if(i-W>=0)\n                Wsum -= dp[i-W];\n        }\n        return res;\n    }\n}\n```
['Math', 'Dynamic Programming', 'Sliding Window', 'Probability and Statistics', 'Java']