O(N) java solution with explanation
\tlet prob[i] denote the probability of reaching the point i\n    w is the maximum coin which we can draw\n\n    the probability of drawing each coin is equal, 
\tlet prob[i] denote the probability of reaching the point i\n    w is the maximum coin which we can draw\n\n    the probability of drawing each coin is equal, so the probability of drawing each coin in 1/w\n    \n    if we want to know the probability of drawing 14, then we can do it as follows\n    prob[13] * probabilityOfDrawing(1) + prob[12]*probabilityOfDrawing(2) + prob[11]*probabilityOfDrawing(3) + prob[10]*probabilityOfDrawing(4) ...\n\n    but all the values probabilityOfDrawing(1) = probabilityOfDrawing(2) = probabilityOfDrawing(3) = probabilityOfDrawing(4) .. = 1/w;\n    so in general \n    prob[n] = (prob[m-1] + prob[m-2] + prob[m-3] + prob[m-4] + ... prob[m-w]) / (w); [taking out that term common]\n    so if we observe, we are calculating the sum of the previous w elements\n\n    but here there is one edge case \n    for example if we are finding prob[21], then we will do something like this:\n\n    if (k = 17)\n    prob[21] = prob[20] * probabilityOfDrawing(1) + ....\n\n    here in this case, we will never draw 1 after we have reached 20 (remember, the game ends as soon as we touch k or we cross k, so as the sum has already crossed k in this case, we will not draw anything from here)\n\n    so while we are calculating the sum of the previous w elements, any element i, which is greater than k will not be considered, because we will never make a jump from that point\n\n    we use sliding window for keeping track of the the sum of previous w values\n\n    and at the end, we calculate prob[k] + prob[k+1] + .... prob[n] (because we wanted probabolity that the final answer is between k to n)\n\n\n```\nclass Solution {\n    public double new21Game(int n, int k, int w) {\n        \n        if(n >= k + w || k == 0 ) return 1.0 ;\n        \n        double[] dp = new double[n+1];\n        dp[0] = 1.0;\n\n        double res = 0.0;\n        double runningSum = dp[0];\n\n        for(int i=1; i<=n; i++) {\n            \n            // at this point, i assume that i have with me the sum of the previous w elements\n            dp[i] = (runningSum * 1.0) / (w);\n            \n            // if the element we are trying to add is less than k, only then we will add\n            if(i < k) {\n                runningSum+=dp[i];\n            } else {\n                // in case the current i is greater than k we will add it to our answer because at the end we need the sum of dp values from k to n\n                res+=dp[i];\n            }\n\n            if(i - w >= 0) {\n                // adjust the tail end\n                runningSum-=dp[i-w];\n            }\n            \n        }\n\n        return res;\n    }\n}\n```
[]