Alice plays the following game, loosely based on the card game "21".

Alice starts with 0 points and draws numbers while she has less than k points. During each draw, she gains an integer number of points randomly from the range [1, maxPts], where maxPts is an integer. Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets k or more points.

Return the probability that Alice has n or fewer points.

Answers within 10-5 of the actual answer are considered accepted.

&nbsp;
Example 1:

Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.


Example 2:

Input: n = 6, k = 1, maxPts = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.


Example 3:

Input: n = 21, k = 17, maxPts = 10
Output: 0.73278


&nbsp;
Constraints:


	0 &lt;= k &lt;= n &lt;= 104
	1 &lt;= maxPts &lt;= 104


class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp = collections.deque([float(i <= n) for i in range(k, k + maxPts)])
        s = sum(dp)
        for i in range(k):
            dp.appendleft(s / maxPts)
            s += dp[0] - dp.pop()

        return dp[0]
class Solution {
    public double new21Game(int n, int k, int maxPts) {
        double[] dp = new double[k + maxPts];
        dp[0] = 1;
        for (int i = 0; i < k; i++){
            for (int j = 1; j <= maxPts; j++){
                dp[i + j] += dp[i] * 1.0 / maxPts;
            }
        }

        double ans = 0;
        for (int i = k; i < k + maxPts && i <= n; i++){
            ans += dp[i];
        }

        return ans;
    }
}
class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if(k==0 || n>=k+maxPts-1)
            return (double) 1;
        vector<double> dp(n+1);
        dp[0]=1;
        double sum = 0;
        for(int i=0; i<n; i++)
        {
            if(i<k)
                sum+=dp[i]; // reach f(2) by directly drawing f(2) or f(1) and f(1) 
            if(i>=maxPts)
                sum-=dp[i-maxPts];
                
            dp[i+1] = sum/maxPts;
        }
        double ret = 0;
        for(int i=k; i<=n; i++)
            ret+=dp[i];
        return ret;
    }
};
var new21Game = function(n, k, maxPts) {
    if (k+maxPts <= n || k===0) return 1;

    let dp = [];
    dp[0] = 1;
    dp[1] = 1/maxPts;

    for (let i = 2; i <= n; i++) {
        dp[i] = 0;

        if (i <= k) {
            dp[i] = (1 + 1/maxPts) * dp[i-1];
        } else {
            dp[i] = dp[i-1];
        }
        if (i > maxPts) {
            dp[i] -= dp[i-maxPts-1] / maxPts;
        }
    }

    return dp.reduce((acc, cur, idx) => {
        if (idx >= k) {
            acc += cur;
        }
        return acc;
    }, 0)
};
New 21 Game