LC 837. New 21 Game
https://leetcode.com/problems/new-21-game/
把公式写出来的时候就容易想到使用滑动窗口来减少计算量了。
# note(yan): dp[n] 表示无论取多少次，取到n的概率
# dp[n] = dp[n-1] * 1/w + dp[n-2] * 1/w + ...d[n-w] *1/w
# 但是(dp[n-1] + .. dp[n-w]) 可以使用sliding window来计算
class Solution:
def new21Game(self, N: int, K: int, W: int) -> float:
if K == 0 or (N - K) >= W:
return 1.0
dp = [0] * (N + 1)
dp[0] = 1.0
sw = 1.0
for i in range(1, N + 1):
dp[i] = 1 / W * sw
if i < K:
sw += dp[i]
if i >= W:
sw -= dp[i - W]
ans = sum(dp[K:])
return round(ans, 5)