# LeetCode 837. New 21 Game

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:**

1 | Input: N = 10, K = 1, W = 10 |

**Example 2:**

1 | Input: N = 6, K = 1, W = 10 |

**Example 3:**

1 | Input: N = 21, K = 17, W = 10 |

**Note:**

`0 <= K <= N <= 10000`

`1 <= W <= 10000`

- Answers will be accepted as correct if they are within
`10^-5`

of the correct answer. - The judging time limit has been reduced for this question.

这道题可以用DP+滑动窗口来解决。

最终获得N点的概率是`[N-W, N-1]`

中每个点数出现的概率×`1/W`

。所以`P(N)=P(N-1)-P(N-W-1)*1/W+P(N-1)*1/W`

，这个步骤类似于把长度为W的窗口往前滑动一格。

要注意`>=K`

的点数要排除掉。最后要把`[K, N]`

的所有概率加起来。

时间复杂度`O(n)`

。

1 | class Solution { |