【LeetCode】837. 新21点

题目

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：

爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。

当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？

链接：https://leetcode-cn.com/problems/new-21-game

思路

代码

class Solution:
    def new21Game(self, N: int, K: int, W: int) -> float:
        dp = [None]*(K+W)
        cusum = 0 # 累积和
        for i in range(K, K+W):
            if i <= N:
                dp[i] = 1
                cusum += dp[i]
            else:
                dp[i] = 0
        for i in range(K-1, -1, -1):
            dp[i] = cusum / W
            cusum += (dp[i] - dp[i+W]) # 改变累积和，因为i向前挪动过了1个单位，再抽一张牌的牌面值最多i-1+w,因此要-dp[i+w]
        return dp[0]