难度：★★★☆☆
类型：数组
方法：动态规划
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
题目
爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。
当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？
示例 1：
输入：N = 10, K = 1, W = 10
输出：1.00000
说明：爱丽丝得到一张卡，然后停止。
示例 2：
输入：N = 6, K = 1, W = 10
输出：0.60000
说明：爱丽丝得到一张卡，然后停止。
在 W = 10 的 6 种可能下，她的得分不超过 N = 6 分。
示例 3：
输入：N = 21, K = 17, W = 10
输出：0.73278
提示：
0 <= K <= N <= 10000
1 <= W <= 10000
如果答案与正确答案的误差不超过 10^-5，则该答案将被视为正确答案通过。
此问题的判断限制时间已经减少。
解答
读懂题意是算法题的关键。
这道题实际上是在求爱丽丝在一个游戏中获胜的概率。
游戏规则有几个关键点需要注意：
游戏的停止的条件是点数总和到达K，而这时点数总和有很多个可能，最小是K，最大能取到K+W-1，因为可以抽取的纸牌中最大的数字也就是W，这样一来，游戏结束时一共会有W种点数总和的可能性，结束时的点数区间为[K, K+W-1]闭区间。
获胜的条件是游戏结束时的点数总和不超过N，根据N与游戏结束时点数区间的关系，有这么几种情况：
N小于K，如果这样的话，游戏结束时其实点数总和已经不小于K了，是不能获胜的；
N大于等于K+W，如果这样，N超过了所有结束时点数总和的可能，因此不论如何都是获胜的；
N在结束时的点数区间，这样就要分情况讨论了。
不过，我们可以用动态规划的方式把以上几种情况归并，接下来看详细介绍。
整个游戏过程中，爱丽丝手中的总点数一共有多少种可能性呢？很显然，从0开始一直到K+W-1，这些点数都是可能取到的。我们又可以把这些点数分成两种类别，一种是游戏过程中的，一种是游戏结束后的。
【数组定义】
定义一维数组dp，维度为K+W，dp[i]表示的是当爱丽丝手中的总点数为i时，可以在游戏中获胜的概率。其中前K个位置所对应的点数（从0到K-1）都可能在游戏过程中出现，后W个位置对应的点数（从K到K+W-1）只能在游戏结束时获得。
【初始状况】
我们可以率先确定的是，dp数组后W个位置的值，因为游戏已经结束了，因此可以按照游戏的规则，把点数不超过N的位置填充成百分之百，意思是如果爱丽丝手中的总点数是当前这个位置，那么一定是获胜的。其他位置填充成零。
【递推公式】
确定了dp数组后W个位置处的值，就可以逐个的填充了，不过这里的顺序是从后往前，也就是从K-1位置开始，一直填充到0位置的。
为了得到爱丽丝手中点数为i时获胜的概率，就要知道这个概率跟什么已知的量有关。很显然，我们知道了当爱丽丝总点数为i+1一直到i+W时获胜的概率，那么就可以知道，他们都可以由手中持有点数为i的情况得到来，而且是概率均等的。这是从必然到偶然，从已知到未知，从后向前的递推计算。
dp[i] = sum(dp[i+1:i+1+W])/W
用一个变量s记录W滑窗中的所有值的和，每次去掉末尾添加头部即可实现更新，避免重复计算。
【返回值】
最后返回爱丽丝手中点数为0时获胜的概率dp[0]即可。
class Solution:
def new21Game(self, N: int, K: int, W: int) -> float:
dp = [0 for _ in range(K)] + [1 if i <= N else 0 for i in range(K, K+W)]
s = sum(dp[K:])
for i in reversed(range(K)):
dp[i] = s/W
s += dp[i]-dp[i+W]
return dp[0]
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
