★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10576171.html 
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Alice plays the following game, loosely based on the card game "21".

Alice starts with 0 points, and draws numbers while she has less than K points.  During each draw, she gains an integer number of points randomly from the range [1, W], where W is an integer.  Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets K or more points.  What is the probability that she has N or less points?

Example 1:

Input: N = 10, K = 1, W = 10
Output: 1.00000
Explanation:  Alice gets a single card, then stops.

Example 2:

Input: N = 6, K = 1, W = 10
Output: 0.60000
Explanation:  Alice gets a single card, then stops.
In 6 out of W = 10 possibilities, she is at or below N = 6 points.

Example 3:

Input: N = 21, K = 17, W = 10
Output: 0.73278

Note:

1. 0 <= K <= N <= 10000
2. 1 <= W <= 10000
3. Answers will be accepted as correct if they are within 10^-5 of the correct answer.
4. The judging time limit has been reduced for this question.

爱丽丝参与一个大致基于纸牌游戏 “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

提示：

1. 0 <= K <= N <= 10000
2. 1 <= W <= 10000
3. 如果答案与正确答案的误差不超过 10^-5，则该答案将被视为正确答案通过。
4. 此问题的判断限制时间已经减少。

24ms

 1 class Solution {
 2     func new21Game(_ N: Int, _ K: Int, _ W: Int) -> Double {
 3         guard N > 0 else { return 1.0 }
 4         guard W >= N - K else { return 1.0 }
 5         var dp = Array(repeating: 0.0, count: N+1)
 6         dp[0] = 1
 7         let w = Double(W)
 8         var temp = 0.0
 9         for i in 1...N {
10             if i <= K {
11               temp += dp[i-1] / w  
12             }
13             if i > W {
14                 temp -= dp[i-W-1] / w
15             } 
16             dp[i] = temp  
17         }
18         return dp[K...].reduce(0.0, +)
19     }
20 }

 1 class Solution {
 2     func new21Game(_ N: Int, _ K: Int, _ W: Int) -> Double {        
 3         if K == 0 || N >= (K + W) {return 1.0}        
 4         var dp:[Double] = [Double](repeating:0.0,count:K + W)
 5         dp[0] = 1.0
 6         for i in 1..<(K + W)
 7         {
 8             dp[i] = dp[i - 1]
 9             if i <= W
10             {
11                 dp[i] += dp[i - 1] / Double(W)
12             }
13             else
14             {
15                 dp[i] += (dp[i - 1] - dp[i - W - 1]) / Double(W)
16             }
17             if i > K
18             {
19                 dp[i] -= (dp[i - 1] - dp[K - 1]) / Double(W)            
20             }            
21         }
22         return dp[N] - dp[K - 1]
23     }
24 }