Sliding window + DP
"""\nSliding window + DP\nRunning Time: O(N)\n\nDefine dp[i] = probability of getting i points\nOptimal Substructure:\n\t\t\n    dp[x] = 1/W * dp[x-1] + 1/W * d
"""\nSliding window + DP\nRunning Time: O(N)\n\nDefine dp[i] = probability of getting i points\nOptimal Substructure:\n\t\t\n    dp[x] = 1/W * dp[x-1] + 1/W * dp[x-2] + 1/W * dp[x-3] + ... + 1/W * dp[x-W]\n    Or: dp[x] = 1/W * (dp[x-1] + dp[x-2] + dp[x-3] + ... + dp[x-W])\n\nSo with dp[0]=1, our base case, we can keep the running_sum = dp[x-1] + dp[x-2] + dp[x-3] + ... + dp[x-W] to calculate dp[x].\n\nNote: When x >= K, Alice stops drawing numbers. So no y > x can be formed from x.\n    So we don\'t include dp[x] into the running_sum when x >= K.\n"""\n```\nclass Solution:\n    def new21Game(self, N, K, W):\n        # Corner cases:\n        if K == 0: return 1\n        if N == 0: return 0\n        if K > N: return 0\n        \n        dp = [0] * (N + 1) # dp[i] means the probability with i points\n        dp[0] = 1\n        \n        # The running sum of the sliding window\n        running_sum = 1\n        p1 = 0\n        for p2 in range(1, N + 1):\n            if p2 - p1 > W:\n                running_sum -= dp[p1]\n                p1 += 1\n            dp[p2] = running_sum * (1/W)\n\n            if p2 < K: running_sum += dp[p2] # When x >= K, Alice stops drawing numbers. So no y > x can be formed from x.\n        return sum(dp[K:N+1])\n```
[]