爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：爱丽丝以0分开始，并在她的得分少于k分时抽取数字。 抽取时，她从[1, maxPts]的范围中随机获得一个整数作为分数进行累计，其中maxPts是一个整数。 每次抽取都是独立的，其结果具有相同的概率。当爱丽丝获得k分 或更多分 时，她就停止抽取数字。爱丽丝的分数不超过n的概率是多少？与实际答案误差不超过10-5的答案将被视为正确答案。
假设 dp[x] 为她手上牌面为x时，能获胜的概率，那么这个概率应该是：
dp[x]=1/w * (dp[x+1]+dp[x+2]+dp[x+3]...+dp[x+w])，此即状态转移方程。
因为抽取的牌面机会都是均等的，她能抽取的面值在 [1,w] 之间，所以将概率之和平均一下就是 dp[x] 的概率。
x 最多能到 k-1，因为当大于等于 k 时，爱丽丝会停止抽牌，所以当游戏结束时，即爱丽丝停止抽牌时，她可能达到的最大牌面是
k+w-1，k-1而一开始她的牌面是0，所以我们用一个长度为 k+w 的 dp 数组来保存她在所有面值下的胜率。最后 dp[0]，也就是最开始爱丽丝还没有抽牌，她的牌面为 0 时的胜率，这个就是我们的答案。
将格子分成了 2 部分 [0,k-1] 和 [k,k+w-1]，区别就是 [0,k-1] 爱丽丝可以抽牌，[k,k+w-1] 时不能抽牌，那么不能抽牌时她获胜的概率是多少呢，此时已不能抽牌，要么赢要么输，很显然牌面小于等于 n 时，概率就是 1，大于 n 概率就是 0，所以先直接填满图中蓝色的格子。
接下来，从
k-1 开始填图中的橘色部分，这个值根据我们前面提到的计算方式，实际上就相当于它后面 w 个格子的总和除以w 。用一个 temp变量来保存累加结果，而下一轮只是减去右边的格子，加上左边的格子即可。
将思路整合，完整代码如下
本文部分内容引用自Mdull的题解，来源于力扣（LeetCode）。
