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, W], where W is an integer.  Each draw is independent and the outcomes have equal probabilities.
Alice stops drawing numbers when she gets K or more points.  What is the probability that she has N or less points?
Example 1:
Input: N = 10, K = 1, W = 10
Output: 1.00000
Explanation:  Alice gets a single card, then stops.

Example 2:
Input: N = 6, K = 1, W = 10
Output: 0.60000
Explanation:  Alice gets a single card, then stops.
In 6 out of W = 10 possibilities, she is at or below N = 6 points.

Example 3:
Input: N = 21, K = 17, W = 10
Output: 0.73278
Note:

0 <= K <= N <= 10000
1 <= W <= 10000
Answers will be accepted as correct if they are within 10^-5 of the correct answer.
The judging time limit has been reduced for this question.

Difficulty: interview

Starter code:

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        

Solutions:
class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        dp = [0] * (N + W)
        for i in range(K, N + 1):
            dp[i] = 1
        
        S = min(W, N - K + 1)
        for i in range(K - 1, -1, -1):
            dp[i] = S / W
            S += dp[i] - dp[i + W]
        return dp[0]

class Solution(object):
    def new21Game(self, N, K, W):
        dp = [0.0] * (N + W + 1)
        # dp[x] = the answer when Alice has x points
        for k in range(K, N + 1):
            dp[k] = 1.0

        S = min(N - K + 1, W)
        # S = dp[k+1] + dp[k+2] + ... + dp[k+W]
        for k in range(K - 1, -1, -1):
            dp[k] = S/W
            S += dp[k] - dp[k + W]

        return dp[0]

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        
        # solution 1: Time and Space both O(N+W)
        # # pseudocode: let dp[x] be the answer when
        # #             Alice already has x points
        # dp[k] = 1.0 when K <= k <= N, else 0.0
        # for k from K-1 to 0:
        #     dp[k] = (dp[k+1] + ... + dp[k+W]) / W
        # return dp[0]
        
        # dp[x] = the answer when Alice has x points
        dp = [0.0] * (N + W + 1)
        for k in range(K, N + 1):
            # Alice wins if has between K and N points
            dp[k] = 1.0

        S = sum(dp[i] for i in range(K, K+W+1))#min(N - K + 1, W) # = dp[K+1] + ... + dp[K+W]
        # S = dp[k+1] + dp[k+2] + ... + dp[k+W]
        for k in reversed(list(range(K))):
            dp[k] = S / float(W)
            S += dp[k] - dp[k + W]

        return dp[0]
        
#         # solution 2: time and space limit exceeded
#         # dp(n, k) = 1 / W * ( sum pt in range(1, W+1) over dp(n-pt, k-pt) )
        
#         memo = {}
#         def dp(n, k):
#             if (n, k) not in memo:
#                 if k <= 0:
#                     ans = int(n >= 0)
#                 else:
#                     ans = 0
#                     for pt in range(1, W+1):
#                         ans += dp(n-pt, k-pt)
#                     ans *= 1. / W
#                 memo[n, k] = ans
#             return memo[n, k]
#         return dp(N, K)



# 837. New 21 Game 

class Solution1:
    def new21Game(self, N: int, K: int, W: int) -> float:

        dp = [None] * (K + W)
        s = 0
        for i in range(K, K + W):          # 填蓝色的格子
            dp[i] = 1 if i <= N else 0
            s += dp[i]
        for i in range(K - 1, -1, -1):      # 填橘黄色格子
            dp[i] = s / W
            s = s - dp[i + W] + dp[i]
        return dp[0]

# 作者：Mcdull0921
# 链接：https://leetcode-cn.com/problems/new-21-game/solution/huan-you-bi-zhe-geng-jian-dan-de-ti-jie-ma-tian-ge/


class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        dp = [1 if i <= N else 0 for i in range(K + W)]
        s = sum(dp[K : K + W])
        for i in range(K-1, -1, -1):
            dp[i] = s / W
            s = s - dp[i + W] + dp[i]
        return dp[0]

class Solution:
    def new21Game(self, N, K, W):
        dp = [0.0] * (N + W + 1)
        # dp[x] = the answer when Alice has x points
        for k in range(K, N + 1):
            dp[k] = 1.0

        S = min(N - K + 1, W)
        # S = dp[k+1] + dp[k+2] + ... + dp[k+W]
        for k in range(K - 1, -1, -1):
            dp[k] = S / float(W)
            S += dp[k] - dp[k + W]

        return dp[0]

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        if K == 0:
            return 1
        dp = [0] * (W + K)
        dp[0] = 1
        sliding_sum = 1
        for i in range(1, K+W):
            # print(sliding_sum)
            # constant = dp[i] / W
            # for j in range(i+1, i+W+1):
            #     dp[j] += constant
            # dp[i] = 0
            dp[i] = sliding_sum / W
            if i < K:
                sliding_sum += dp[i]
            if i-W >= 0:
                sliding_sum -= dp[i-W]
                dp[i-W] = 0
        # print(dp)
        return sum(dp[K:N+1])/ sum(dp)
                


class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        if K == 0:
            return 1
        
        dp = [0]
        cur, temp = 1, 1/W
        for i in range(1, W+1):
            dp.append(cur/W)
            if i < K:
                cur += dp[-1]
            
        # print(dp)
        total = sum(dp[1:min(W+1, K)])
        left = 1
        for i in range(W+1, W+K):
            dp.append(total/W)
            total -=  dp[left]
            left += 1
            if i < K:
                total += dp[-1]
        # print(dp)
        end = sum(dp[K:])
        good_end = sum(dp[K:N+1])
        return good_end/end


class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        if K==0 or K-1+W<=N:
            return 1
        dp=[1]+[0]*N
        cursum=1
        for i in range(1,N+1):
            # dp[i]=sum(dp[max(0,i-W):min(i,K)])*(1/W)
            dp[i]=cursum*(1/W)
            if i<K:
                cursum+=dp[i]
            if i>=W:
                cursum-=dp[i-W]
        return sum(dp[K:])

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        # O(N + W), https://www.youtube.com/watch?v=bd0t6cj7_4E
        # Let dp(x) be the answer when we already have x points.
        dp = [0] * (N + W + 1)
        
        for i in range(K, N + 1):
            dp[i] = 1.0
        
        s = N - K + 1 # How many 1.0s
        # dp[k] = 1 / W * (dp[k+1] + dp[k+2] + ... + dp[k+W])
        for i in range(K - 1, -1, -1):
            dp[i] = s / W
            # s = 0
            # for j in range(W):
                # s += dp[i + j + 1]
            # dp[i] = s / W
            s += dp[i] - dp[i + W]
        
        return dp[0]

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        dp = [0.0] * (N + W + 1)
        # dp[x] = the answer when Alice has x points
        for k in range(K, N + 1):
            dp[k] = 1.0

        S = min(N - K + 1, W)
        # S = dp[k+1] + dp[k+2] + ... + dp[k+W]
        for k in range(K - 1, -1, -1):
            dp[k] = S / float(W)
            S += dp[k] - dp[k + W]

        return dp[0]

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        #probability of falling into [K, K + 1, ..., N]
        #P[i] = 1/W*(P[i - 1] + ... + P[i - W])
        #running_sum: P[i - 1] + ... + P[i - W]
        if K == 0:
            return 1
        running_sum = 1
        P = [1]
        for i in range(1, W):
            P.append(1/W * running_sum)
            running_sum += P[-1]
        # print(P)
        for i in range(W, K):
            P.append(1/W * running_sum)
            running_sum += (P[-1] - P[i-W])
        # print(P)
        res = 0
        #17: = 1/W*(P[7] + ... + P[16])
        #18: = 1/W*(P[8] + ... + P[16])
        #19: = 1/W*(P[9] + ... + P[16])
        
        #At 7: 1/W chance (7 + 10)
        #8: 2/W chance (8 + 9, 8 + 10)
        #9: 3/W (9 + 8, 9 + 9, 9 + 10)
        #15: 5/W (15 + 2, ..., 15 + 6)
        #16: 5/W   (16 + 1, ..., 16 + 5)
        running_sum = sum(P[max(0, K - W): K])
        # print(sum(P[0:1]))
        # print(\"running_sum = {0}\".format(running_sum))
        # print(sum(P[7:17]) + sum(P[8:17]) + sum(P[9:17]) + sum(P[10:17]) + sum(P[11:17]))
        # print(1*P[7] + 2*P[8] + 3*P[9] + 4*P[10] + 5*sum(P[11:17]))
        
        #12: (P[2] + ... + P[11])*1/W
        #13: (P[3] + ... + P[11])*1/W
        #14: (P[4] + ... + P[11])*1/W
        print(sum(P[2:12]) + sum(P[3:12]) + sum(P[4:12])+  sum(P[5:12]) + sum(P[6:12]) + sum(P[7:12]) + sum(P[8:12]) + sum(P[9:12]) + sum(P[10:12]) + sum(P[11:12]))
        #From 2: 2 + 10
        #From 3: 3 + 9, 3 + 10
        #From 4: 4 + 8, 4 + 9, 4 + 10
        #From 11: 11 + 1, ..., 11 + 10
        for i in range(max(0, K - W), K):
            #from i: can go from max(i + 1, K) to min(i + 10, N)
            res += P[i]/W * max((min(i + W, N) - max(i + 1, K) + 1), 0)
            # print(res)
        # for i in range(K, min(N + 1, K + W)):
        #     res += (1/W * running_sum)
        #     if i >= W:
        #         running_sum -= P[i - W]
        # # print(sum(P[1:11]))
        return res

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        #probability of falling into [K, K + 1, ..., N]
        #P[i] = 1/W*(P[i - 1] + ... + P[i - W])
        #running_sum: P[i - 1] + ... + P[i - W]
        if K == 0:
            return 1
        running_sum = 1
        P = [1]
        for i in range(1, W):
            P.append(1/W * running_sum)
            running_sum += P[-1]
        # print(P)
        for i in range(W, K):
            P.append(1/W * running_sum)
            running_sum += (P[-1] - P[i-W])
        # print(P)
        res = 0
        #17: = 1/W*(P[7] + ... + P[16])
        #18: = 1/W*(P[8] + ... + P[16])
        #19: = 1/W*(P[9] + ... + P[16])
        
        #At 7: 1/W chance (7 + 10)
        #8: 2/W chance (8 + 9, 8 + 10)
        #9: 3/W (9 + 8, 9 + 9, 9 + 10)
        #15: 5/W (15 + 2, ..., 15 + 6)
        #16: 5/W   (16 + 1, ..., 16 + 5)
        running_sum = sum(P[max(0, K - W): K])
        # print(sum(P[0:1]))
        # print(\"running_sum = {0}\".format(running_sum))
        # print(sum(P[7:17]) + sum(P[8:17]) + sum(P[9:17]) + sum(P[10:17]) + sum(P[11:17]))
        # print(1*P[7] + 2*P[8] + 3*P[9] + 4*P[10] + 5*sum(P[11:17]))
        
        #12: (P[2] + ... + P[11])*1/W
        #13: (P[3] + ... + P[11])*1/W
        #14: (P[4] + ... + P[11])*1/W
        print(sum(P[2:12]) + sum(P[3:12]) + sum(P[4:12])+  sum(P[5:12]) + sum(P[6:12]) + sum(P[7:12]) + sum(P[8:12]) + sum(P[9:12]) + sum(P[10:12]) + sum(P[11:12]))
        #From 2: 2 + 10
        #From 3: 3 + 9, 3 + 10
        #From 4: 4 + 8, 4 + 9, 4 + 10
        #From 11: 11 + 1, ..., 11 + 10
        
        
        #Last number candidates: From max(0, K - W) to K - 1
        #From candidate i, we can go from max(i + 1, K) to min(i + W, N) 
        #so there are min(i + W, N) - max(i + 1, K) + 1 options
        for i in range(max(0, K - W), K):
            #from i: can go from max(i + 1, K) to min(i + 10, N)
            res += P[i]/W * max((min(i + W, N) - max(i + 1, K) + 1), 0)
            # print(res)
        # for i in range(K, min(N + 1, K + W)):
        #     res += (1/W * running_sum)
        #     if i >= W:
        #         running_sum -= P[i - W]
        # # print(sum(P[1:11]))
        return res

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        if N > K + W - 1 or K == 0: return 1
        
        dp = [0] * (K + W)
        dp[1] = 1 / W
        for i in range(2, K + 1):
            if i == W + 1:
                dp[i] = dp[i - 1] + (dp[W] - 1) / W
            else:
                dp[i] = ((W + 1) * dp[i - 1] - (dp[i - 1 - W] if i >= W + 1 else 0)) / W
        for i in range(K + 1, K + W):
            dp[i] = dp[i - 1] - (dp[i - W - 1] if i - W >= 2 else 0) / W
            if i == W + 1: dp[i] -= 1 / W
        res = sum(dp[i] for i in range(K, N + 1)) / sum(dp[i] for i in range(K, K + W))
        return res

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        if N >= K + W - 1:
            return 1
        if N < K:
            return 0
        if K == 0:
            return 1
            
        probs = [0]*(W+2)
        probs[0] = 1
        probs[1] = 1/W
        for i in range(1,K):
            probs[(i+1)%(W+2)] = probs[i%(W+2)]*(W+1)/W - probs[(i+2)%(W+2)]/W
        for i in range(W):
            probs[(K+i+1)%(W+2)] = probs[(K+i)%(W+2)] - probs[(K+i+2)%(W+2)]/W
        
        if K%(W+2) < (N+1)%(W+2):
            return sum(probs[K%(W+2):(N+1)%(W+2)])
        else:
            return sum(probs[K%(W+2):]) + sum(probs[:(N+1)%(W+2)])

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        if N < K:
            return 0
        if N > K - 1 + W:
            return 1
        dp = [0] * (K + W)
        for k in range(K, N + 1):
            dp[k] = 1
        
        S = N - K + 1
        for k in range(K - 1, -1, -1):
            dp[k] = S/W
            S += dp[k] - dp[k + W]
        return dp[0]
        


class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        
        if K == 0:
            return 1.0
        
        if K-1+W <= N:
            return 1.0
        
        prob = [0.0] * (K+W)
        avg = 0
        for i in range(W):
            prob[K+i] = float(K+i <= N)
            avg += prob[K+i] / W
            
        for i in range(K)[::-1]:
            prob[i] += avg
            avg += (prob[i] - prob[i+W]) / W
            
        return prob[0]

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
#         probs = [0] * (n + 1)
#         probs[0] = 1
        
#         prob = 1 / w
        
            
#         for i in range(k):
#             for j in range(1, w + 1):
#                 if i + j <= n:
#                     probs[i + j] += probs[i] * prob
        
#         return sum(probs[k : n + 1])
        
        dp = [0.0] * (N + W + 1)
        # dp[x] = the answer when Alice has x points
        for k in range(K, N + 1):
            dp[k] = 1.0

        S = min(N - K + 1, W)
        # S = dp[k+1] + dp[k+2] + ... + dp[k+W]
        for k in range(K - 1, -1, -1):
            dp[k] = S / float(W)
            S += dp[k] - dp[k + W]

        return dp[0]

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        dp = [0.0] * (N + W + 1)
        # dp[x] = the answer when Alice has x points
        for k in range(K, N + 1):
            dp[k] = 1.0

        S = min(N - K + 1, W)
        # # S = dp[k+1] + dp[k+2] + ... + dp[k+W]
        for k in range(K - 1, -1, -1):
            dp[k] = S/float(W)
            S = S + dp[k] - dp[k+W]
            

        return dp[0]