# LeetCode 837: New 21 Game

## Problem Restatement

Alice starts with `0` points.

While her score is less than `k`, she keeps drawing a random number from `1` to `maxPts`.

Each draw is independent, and every number from `1` to `maxPts` has the same probability.

Alice stops drawing as soon as her score is at least `k`.

Return the probability that Alice ends with `n` or fewer points.

Answers within `10^-5` of the correct answer are accepted.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integers `n`, `k`, and `maxPts` |
| Output | Probability that Alice ends with score `<= n` |
| Draw range | Each draw gives a number from `1` to `maxPts` |
| Stop rule | Alice stops once score is at least `k` |
| Accepted error | `10^-5` |

Function shape:

```python
class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        ...
```

## Examples

Example 1:

```python
n = 10
k = 1
maxPts = 10
```

Alice draws exactly once, because after the first draw her score is at least `1`.

The draw is between `1` and `10`.

Every possible final score is at most `10`.

So the answer is:

```python
1.0
```

Example 2:

```python
n = 6
k = 1
maxPts = 10
```

Alice draws exactly once.

The final score is one of:

```python
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
```

Only `1` through `6` are valid.

So the probability is:

```python
6 / 10 = 0.6
```

Example 3:

```python
n = 21
k = 17
maxPts = 10
```

The answer is approximately:

```python
0.73278
```

## First Thought: Recursive Probability

Let:

```python
dp[x]
```

mean the probability of eventually ending with score at most `n`, starting from score `x`.

If `x >= k`, Alice stops immediately.

So:

```python
dp[x] = 1, if x <= n
dp[x] = 0, if x > n
```

If `x < k`, Alice draws a number from `1` to `maxPts`.

So:

```python
dp[x] = (dp[x + 1] + dp[x + 2] + ... + dp[x + maxPts]) / maxPts
```

This is correct, but computing every sum directly is too slow.

## Problem With Direct DP

For every score `x`, direct DP may sum `maxPts` future states.

That gives:

```python
O(k * maxPts)
```

This can be too large.

We need to reuse the sum of nearby DP values.

## Key Insight

The recurrence uses a moving window:

```python
dp[x] = average of dp[x + 1] through dp[x + maxPts]
```

When moving from one `x` to the next, most of the window stays the same.

So we can maintain a sliding sum instead of recomputing the whole sum.

There is also a useful forward version.

Let:

```python
dp[i]
```

be the probability that Alice reaches exactly score `i`.

Initially:

```python
dp[0] = 1
```

A score `i` can be reached from previous scores:

```python
i - 1, i - 2, ..., i - maxPts
```

but only previous scores less than `k` can draw again.

So we maintain:

```python
window_sum = sum of probabilities of active previous scores
```

Then:

```python
dp[i] = window_sum / maxPts
```

## Algorithm

Handle the easy winning case first.

If:

```python
k == 0
```

Alice never draws, so her score is `0`, and the answer is `1`.

Also, the maximum possible final score is:

```python
k - 1 + maxPts
```

because Alice can draw only while her score is at most `k - 1`, then she may draw up to `maxPts`.

If:

```python
n >= k - 1 + maxPts
```

then every possible final score is at most `n`, so the answer is `1`.

Otherwise:

1. Create `dp` where `dp[i]` is the probability of reaching score `i`.
2. Set `dp[0] = 1`.
3. Set `window_sum = 1`.
4. For each score `i` from `1` to `n`:
   1. Set `dp[i] = window_sum / maxPts`.
   2. If `i < k`, add `dp[i]` to `window_sum`.
   3. If `i - maxPts >= 0`, remove `dp[i - maxPts]` from `window_sum`.
   4. If `i >= k`, add `dp[i]` to the answer.

## Walkthrough

Use:

```python
n = 6
k = 1
maxPts = 10
```

Alice starts at `0`.

Since `0 < k`, she draws once.

Each result from `1` to `10` has probability:

```python
1 / 10
```

Valid final scores are:

```python
1, 2, 3, 4, 5, 6
```

There are `6` valid scores, each with probability `0.1`.

So:

```python
answer = 6 * 0.1 = 0.6
```

The DP computes the same value.

For `i = 1` through `6`, each `dp[i]` receives:

```python
dp[0] / 10 = 0.1
```

Since all these scores are at least `k`, they are final scores.

The answer becomes:

```python
0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 = 0.6
```

## Correctness

The value `dp[i]` represents the probability that Alice reaches score `i`.

The initial state is correct because Alice starts at score `0`, so `dp[0] = 1`.

A score `i` can be reached only from a previous score `j` where:

```python
1 <= i - j <= maxPts
```

and Alice must still be drawing at `j`, which requires:

```python
j < k
```

Each active previous score contributes:

```python
dp[j] / maxPts
```

to `dp[i]`.

The sliding window stores exactly the sum of these active previous probabilities. Therefore, assigning:

```python
dp[i] = window_sum / maxPts
```

computes the correct probability of reaching score `i`.

When `i < k`, Alice may draw again from score `i`, so `dp[i]` is added to the active window.

When `i >= k`, Alice stops at score `i`, so `dp[i]` is added to the answer instead.

The window also removes scores more than `maxPts` behind, because they can no longer reach the current or future score with one draw.

Thus every final score from `k` through `n` is counted once, and no non-final or too-large score is counted. The returned sum is exactly the probability that Alice ends with score at most `n`.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We compute each `dp[i]` once |
| Space | `O(n)` | We store the probability array |

## Implementation

```python
class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k - 1 + maxPts:
            return 1.0

        dp = [0.0] * (n + 1)
        dp[0] = 1.0

        window_sum = 1.0
        answer = 0.0

        for score in range(1, n + 1):
            dp[score] = window_sum / maxPts

            if score < k:
                window_sum += dp[score]
            else:
                answer += dp[score]

            if score - maxPts >= 0:
                window_sum -= dp[score - maxPts]

        return answer
```

## Code Explanation

The early return handles cases where Alice always wins:

```python
if k == 0 or n >= k - 1 + maxPts:
    return 1.0
```

`dp[score]` stores the probability of reaching exactly `score`:

```python
dp = [0.0] * (n + 1)
dp[0] = 1.0
```

The sliding sum starts with score `0`, because Alice can draw from score `0`:

```python
window_sum = 1.0
```

For each score:

```python
dp[score] = window_sum / maxPts
```

This distributes probability from all active previous scores.

If `score < k`, Alice can still draw from this score:

```python
window_sum += dp[score]
```

If `score >= k`, this is a stopping score:

```python
answer += dp[score]
```

Finally, remove scores that are too far behind:

```python
if score - maxPts >= 0:
    window_sum -= dp[score - maxPts]
```

## Testing

```python
def almost_equal(a: float, b: float, eps: float = 1e-5) -> bool:
    return abs(a - b) <= eps

def run_tests():
    s = Solution()

    assert almost_equal(s.new21Game(10, 1, 10), 1.0)
    assert almost_equal(s.new21Game(6, 1, 10), 0.6)
    assert almost_equal(s.new21Game(21, 17, 10), 0.73278)
    assert almost_equal(s.new21Game(0, 0, 1), 1.0)
    assert almost_equal(s.new21Game(1, 0, 1), 1.0)
    assert almost_equal(s.new21Game(5, 2, 3), 1.0)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `(10, 1, 10)` | All one-draw outcomes are valid |
| `(6, 1, 10)` | Only six of ten one-draw outcomes are valid |
| `(21, 17, 10)` | Standard larger probability case |
| `k = 0` | Alice never draws |
| Small guaranteed win | Confirms early return |
| Maximum final score within `n` | Confirms always-win case |