My take on how to reach at Solution
Firstly, observe that when Alice is done playing, her points can be in range [K, K+W-1]. She can\'t get past K+W because she stops playing when she is at K or m
Firstly, observe that when Alice is done playing, her points can be in range [K, K+W-1]. She can\'t get past K+W because she stops playing when she is at K or more.\n\nNow, we will see how to find the probabilities to stay in the positions in the above range and store them in p[] array.\n\nWe need to know the probabilities of all elems in range [0,K] first. From there we can calculate for elems in range (K, K+W-1]\n\nFor positions  x <= K,\np[x] = (p[x-1] + p[x-2] + ..... + p[x-W]) * (1/W); (Probabilities of previous possible positions to get to x, multiplied by probability of choosing an elem to get to x)\n\nFor implementation, we can keep track past values using a single variable. For each new positions, we will subtract p[x-W-1] and add p[x-1]. Look at implementation below\n\nFor positions x > K,\np[x] = (p[K-1] + p[K-2] + .... + p[x - W]) * 1/W; (Since, we can\'t/shouldn\'t reach x from >= K positions)\n\n\'\'\'\npublic double new21Game(int N, int K, int W) {\n        \n        if(N >= K+W-1) return 1.0; // all possibilities of positions after alice stops playing are from [K, K+W-1]\n        \n        double p[] = new double[K+W];\n        double prob = 1/(W+0.0); // single elem probability\n        \n        double prev = 0;\n        \n        p[0] = 1; // Since we start from 0, initialize it to 1\n        \n\t     //Until K\n        for(int i = 1; i <= K; i++) {\n            prev = prev - (i-W-1 >= 0 ? p[i - W -1] : 0) + p[i-1];\n            p[i] = prev*prob;\n        }\n        \n        double req = p[K];\n        \n\t    // From K+1, we don\'t add the p[i-1] term here as it is >= K\n        for(int i = K+1; i <= N; i++) {\n            prev = prev - (i-W-1 >= 0 ? p[i - W -1] : 0);\n            p[i] = prev * prob;\n            req += p[i];\n            //System.out.println(p[i]);\n        }\n        \n        return req;\n    }\n\'\'\'\n\nPlease comment below, if you didn\'t understand something. I will try to clarify.\n
[]