C++
While Alice has less than k, she will keep drawing. On the last turn, k-1, she could draw the maximum number, maxPts (w), so the maximum she can ever draw is k-
While Alice has less than k, she will keep drawing. On the last turn, k-1, she could draw the maximum number, maxPts (w), so the maximum she can ever draw is k-1+w.\n\nIf n is >= k-1+w, then it will always be true.\n\nWe can have a dp of 0 -> k+w-1, where dp[i] gives the probability that we can i or less.\n\ndp[0] is the base case, we start with 0, so the probabiltiy is 100%.\n\nAt dp[1], we have 1/w chance to draw a 1.\nAt dp[8], we have:\n    dp[1] chance to draw a 1, then 1/w chance to draw a 7 to make it 8. \n    dp[2] chance to draw a 2, then 1/w chance to draw a 6 to make it 8.\n    ...\n    dp[7] chance to draw a 7, then 1/w chance to draw a 1 to make it 8.\n    + drawing an 8 to make 8.\nSo formula become dp[0] * 1/w, dp[1] * 1/w + dp[2] * 1/w + dp[3] * 1/w ....\nOr, (dp[0], dp[1] + dp[2] + dp[3] ... dp[7]) * 1/w.\n\nKeep in mind we only go back max w steps, as that is that maximum points we can draw.\n\n# Code\n```\nclass Solution {\npublic:\n    double new21Game(int n, int k, int w) {\n        if (n >= k+w-1) return 1.0;\n        vector<double> dp(k+w);\n        dp[0] = 1;\n        double p = 1/(double)w;\n\n        double cur = 0;\n        for (int i = 1; i <= k; i++) {\n            if (i-w-1 >= 0) cur -= dp[i-w-1];\n            cur += dp[i-1];\n            dp[i] = cur * p;\n        }\n        double ans = dp[k];\n\n        for (int i = k+1; i <= n; i++) {\n            if (i-w-1 >= 0) cur -= dp[i-w-1];\n            dp[i] = cur * p;\n            ans += dp[i];\n        }\n\n        return ans;\n    }\n};\n```
['C++']