难度: Medium
爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。 抽取时，她从 [1, maxPts] 的范围中随机获得一个整数作为分数进行累计，其中 maxPts 是一个整数。 每次抽取都是独立的，其结果具有相同的概率。
当爱丽丝获得 k 分 或更多分 时，她就停止抽取数字。
爱丽丝的分数不超过 n 的概率是多少？
与实际答案误差不超过 10-5 的答案将被视为正确答案。
示例 1：
输入：n = 10, k = 1, maxPts = 10 输出：1.00000 解释：爱丽丝得到一张牌，然后停止。
示例 2：
输入：n = 6, k = 1, maxPts = 10 输出：0.60000 解释：爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。
示例 3：
输入：n = 21, k = 17, maxPts = 10 输出：0.73278
提示：
0 <= k <= n <= 1041 <= maxPts <= 104运行时间: 49 ms
内存: 16.4 MB
class Solution:
def new21Game(self, n: int, k: int, p: int) -> float:
if n >= k + p - 1:
return 1.0
dp = [0.0] * (k + p)
for i in range(k, n + 1):
dp[i] = 1.0
cur = n - k + 1
for i in range(k)[::-1]:
dp[i] = cur / p
cur += dp[i] - dp[i + p]
return dp[0]
这个题解使用动态规划来解决问题。首先，如果n大于等于k+p-1，意味着爱丽丝可以在不超过n的情况下达到或超过k分，因此返回1.0。对于其他情况，使用一个大小为k+p的数组dp来存储在每个得分i处获得得分不超过n的概率。初始化dp数组中k到n的索引值为1.0，因为这些得分直接导致游戏停止且不会超过n。然后，从k-1倒推到0计算每个得分的概率，使用滑动窗口和cur来跟踪累计概率，以减少重复计算，提高效率。
时间复杂度: O(k+p)
空间复杂度: O(k+p)
class Solution:
def new21Game(self, n: int, k: int, p: int) -> float:
if n >= k + p - 1:
return 1.0 # 直接返回1.0，因为所有分数都有效
dp = [0.0] * (k + p) # 初始化动态规划数组
for i in range(k, n + 1):
dp[i] = 1.0 # 设置得分直接导致停止的情况的概率为1
cur = n - k + 1 # 初始化滑动窗口的累计概率和
for i in range(k)[::-1]:
dp[i] = cur / p # 计算当前分数的概率
cur += dp[i] - dp[i + p] # 更新滑动窗口的累计概率和
return dp[0] # 返回从0分开始的概率
在游戏中，Alice每次可以抽取的分数从1到p，因此在得分达到k之后Alice将不再抽取分数。如果n（即最大允许的分数总和）大于或等于k+p-1，这意味着即使Alice在得分为k-1时抽取了最大的p分（即最不利的情况），她的总分数也只是k-1+p，这等于k+p-1。如果k+p-1都不会超过n，那么从任何低于k的分数出发，Alice抽取分数后得到的总分数都不可能超过n，因此在这种情况下，Alice无论如何都不会超过n分，从而保证了她的胜率为100%，即概率为1.0。
在动态规划中，dp数组的每一个元素dp[i]代表从得分i开始游戏，最终得分不超过n的概率。当得分i达到或超过k时，Alice将不再抽取新的分数，游戏停止。如果此时的得分i处于k到n之间，由于没有进一步抽取的机会，这些得分直接导致游戏结束，且这些得分都没有超过n，因此这些情况的概率为1.0。这是因为在这些得分下，Alice已经停止抽取，不存在超过n的风险。
在计算dp[i]时，我们需要考虑从i+1到i+p每个分数的概率，因为Alice在得分i时抽取1到p分的任意一个都可能发生。为了有效地计算这一系列概率的总和，我们使用滑动窗口（即变量cur）来维护这个概率的累积和。具体来说，当从i+1推移到i时，我们需要添加dp[i]（新进入窗口的概率）并移除dp[i+p]（离开窗口的概率），这样就可以快速更新cur的值而不需要重复计算。这样的操作大大提高了计算效率，避免了对每个i都进行p次加法的重复计算。