837

class Solution {
public:
    double new21Game(int n, int k, int w) {
        if(k == 0 || n >= k+w) return 1.0;
        vector<double> dp(n+1);
        dp[0] = 1.0;
        double wSum=1.0, res=0.0;

        for(int i=1; i<=n; i++){
            dp[i] = wSum/w;
            if(i<k) wSum += dp[i];
            if(i-w >= 0) wSum -= dp[i-w];
        }
        for(int i=k; i<=n; i++)
            res += dp[i];
        return res;
    }
};