> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/837.-new-21-game.md).

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

```
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.

{% hint style="info" %}
Dynamic programming用到一個DP array，dp\[i]紀錄點數和為i的機率。\
dp\[i] = dp\[i - W] \* (1 / W) + dp\[i - (W - 1)] \* (1 / W) + ... + dp\[i - 2] \* (1 / W) + dp\[i - 1] \* (1 / W) = (dp\[i - W] + dp\[i - (W - 1)] + ... + dp\[i - 1]) \* (1 / W) = Wsum / W\
再用一個變數Wsum紀錄一個大小最大為W的sliding window，紀錄前K個點數和的機率。
{% endhint %}

```cpp
// Dynamic Programming
double new21Game(int N, int K, int W) { // time: O(N); space: O(N)
    if (K == 0 || N >= K + W) return 1.0;
    double res = 0.0, Wsum = 1.0;
    vector<double> dp(N + 1, 0.0);
    dp[0] = 1.0;
    for (int i = 1; i <= N; ++i) {
        dp[i] = Wsum / W;
        if (i < K) Wsum += dp[i];
        else res += dp[i];
        if (i - W >= 0) Wsum -= dp[i - W];
    }
    return res;
}
```