C++ bottom-up DP solution
\nclass Solution {\npublic:\n    double new21Game(int N, int K, int W) {\n        // Max score is K + W - 1 points.\n        const int last_score = min(N, K + W
```\nclass Solution {\npublic:\n    double new21Game(int N, int K, int W) {\n        // Max score is K + W - 1 points.\n        const int last_score = min(N, K + W - 1);\n        // dp[n] is the probability that score n will be reached at some point.\n        std::vector<double> dp(last_score + 2);\n        // Since the game starts at score 0, dp[0] is 100%.\n        dp[0] = 1.0;\n        // dp[n] = sum(dp from n-W to n-1)/W, since we can reach score n by being\n        // at score n-1 and drawing a 1, or being at score n-2 and drawing a 2, and\n        // so on. The chance of being at score n-i and drawing an i is dp[n-i]/W.\n        // However, if we\'ve stopped drawing, then we need to sum from n-W to K-1.\n        // So properly, dp[n] = sum(dp from max(n-W, 0) to min(n-1, K))/W.\n        \n        // wsum, the windowed sum, is the sum or the last W elements, or properly\n        // sum(dp from max(n-W, 0) to min(n-1, K)). The next element is wsum/W.\n        double wsum = 0.0;\n        \n        for (int i=0; i <= last_score; ++i) { // Windowed.\n            if (i < K) {\n                // Only add to wsum if we\'re still drawing.\n                wsum += dp[i];\n            }\n            if (i - W >= 0) {\n                // Delete last element from window.\n                wsum -= dp[i - W];\n            }\n            dp[i+1] = wsum/W;\n        }\n        \n        // The final result is the sum of dp in range [K, N], since the set of\n        // possible end scores are K to K + W - 1, (as such the sum of dp from K\n        // to K + W - 1 should be 1.0 if we actually computed the whole vector) and\n        // we\'re looking for the chance of ending up with a score below or equal to N.\n        // Therefore, the chance of getting N or less points is the chance of ending\n        // at K (dp[K]), plus the chance of ending at K+1, and so on up to N.\n        return std::accumulate(dp.begin()+K, dp.begin()+N+1, 0.0);\n    }\n};\n```
['Dynamic Programming', 'C']