# New 21 Game
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/new-21-game)
Canonical: https://scaleengineer.com/dsa/problems/new-21-game
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Probability and Statistics](https://scaleengineer.com/dsa/patterns/probability-and-statistics)
---
## Problem
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, maxPts]`, where `maxPts` is an integer. Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets `k` **or more points**.

Return the probability that Alice has `n` or fewer points.

Answers within `10-5` of the actual answer are considered accepted.

**Example 1:**

**Input:** n = 10, k = 1, maxPts = 10
**Output:** 1.00000
**Explanation:** Alice gets a single card, then stops.

**Example 2:**

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

**Example 3:**

**Input:** n = 21, k = 17, maxPts = 10
**Output:** 0.73278

**Constraints:**

* `0 <= k <= n <= 104`
* `1 <= maxPts <= 104`

# Approaches
## Naive Dynamic Programming
This approach uses dynamic programming to solve the problem. We define `dp[i]` as the probability of reaching a score of exactly `i`. We build up the `dp` table from `dp[0]` up to `dp[n]`. The final answer is the sum of probabilities of stopping at scores from `k` to `n`.
**Time:** O(n * maxPts). The outer loop runs `n` times, and the inner loop runs `maxPts` times. · **Space:** O(n) to store the `dp` array.
**Pros:** Simple to understand and implement.; Directly follows the problem's state transitions.
**Cons:** Inefficient due to nested loops.; Time complexity is high, likely leading to 'Time Limit Exceeded' on larger test cases.
### Explanation
Let `dp[i]` be the probability of having a score of `i` at some point.

The base case is `dp[0] = 1.0`, as Alice starts with 0 points with certainty. All other `dp` values are initialized to 0.

To calculate `dp[i]`, we consider all possible previous scores `p` from which we could reach `i` by drawing a single card `j`. The value of `j` can be from 1 to `maxPts`. So, `p = i - j`.

A crucial rule is that Alice only draws a card if her current score is less than `k`. Therefore, the previous score `p` must be less than `k`.

The probability of drawing any specific card `j` is `1 / maxPts`.

The recurrence relation is: `dp[i] = sum(dp[i-j] / maxPts)` for `j` from 1 to `maxPts`, provided `i-j >= 0` and `i-j < k`.

We iterate from `i = 1` to `n`, and for each `i`, we iterate from `j = 1` to `maxPts` to sum up the probabilities.

After computing all `dp[i]` up to `n`, the probability of stopping at a score `i` (where `i >= k`) is exactly `dp[i]`. This is because to reach `i >= k`, the previous score must have been `< k`.

The final answer is the sum of probabilities of stopping at any score between `k` and `n`, inclusive. This is `sum(dp[i])` for `i` from `k` to `n`.

```java
public double new21Game(int n, int k, int maxPts) {
    if (k == 0 || n >= k + maxPts - 1) {
        return 1.0;
    }
    double[] dp = new double[n + 1];
    dp[0] = 1.0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= maxPts; j++) {
            if (i - j >= 0 && i - j < k) {
                dp[i] += dp[i - j] / maxPts;
            }
        }
    }

    double probability = 0.0;
    for (int i = k; i <= n; i++) {
        probability += dp[i];
    }
    return probability;
}
```
### Algorithm
- 1. Handle the edge case where the answer is trivially 1.0 (if `k=0` or `n >= k + maxPts - 1`).
- 2. Initialize a `dp` array of size `n+1` to store probabilities. Set `dp[0] = 1.0`.
- 3. Iterate `i` from 1 to `n`.
- 4. Inside this loop, iterate `j` from 1 to `maxPts`.
- 5. If the previous score `p = i - j` is valid (i.e., `p >= 0` and `p < k`), add `dp[p] / maxPts` to `dp[i]`.
- 6. After filling the `dp` array, initialize a variable `result = 0.0`.
- 7. Iterate `i` from `k` to `n` and sum up `dp[i]` into `result`.
- 8. Return `result`.

## Dynamic Programming with Sliding Window
This approach optimizes the naive DP solution. We observe that the calculation of `dp[i]` involves summing up a window of previous `dp` values. Instead of re-calculating this sum every time, we can maintain the sum in a 'sliding window' and update it in `O(1)` time for each step.
**Time:** O(n). We iterate through the scores from 1 to `n` once, and all operations inside the loop are constant time. · **Space:** O(n) for the `dp` array. We need to store `dp` values because `dp[i]` depends on `dp[i-maxPts]`.
**Pros:** Highly efficient with linear time complexity.; Passes all test cases within the time limit.
**Cons:** The logic for updating the sliding window sum can be slightly tricky to get right, especially around the `k` boundary.
### Explanation
The recurrence `dp[i] = (1/maxPts) * sum(dp[p])` for `p` in a certain range suggests an optimization. The sum is over a contiguous block of previous `dp` values.

Let `windowSum` be the sum of probabilities of scores from which Alice is allowed to draw a card. Initially, Alice is at score 0, so `dp[0] = 1.0` and `windowSum = 1.0`.

We iterate from `i = 1` to `n`. At each step `i`, `dp[i]` is calculated as `windowSum / maxPts`.

After calculating `dp[i]`, we update `windowSum` for the next iteration `i+1`. The new window for `i+1` is `[i+1-maxPts, i]`. Compared to the window for `i` (`[i-maxPts, i-1]`), we add `dp[i]` and remove `dp[i-maxPts]`.

The update rule for `windowSum` depends on whether we can continue drawing from score `i`.
- If `i < k`, we can continue drawing. So, we add `dp[i]` to `windowSum`.
- If `i >= k`, we must stop. `dp[i]` represents the probability of a final state. We add it to our final `result` but *not* to `windowSum`, because we cannot draw any more cards from this state.

As we slide the window, we also need to subtract the term that falls out of the window's left end. If `i >= maxPts`, we subtract `dp[i - maxPts]` from `windowSum`.

This way, `windowSum` is always maintained as `sum(dp[j])` over the relevant window, and each `dp[i]` is computed in `O(1)` time.

The final result is the sum of `dp[i]` for `i` from `k` to `n`.

```java
public double new21Game(int n, int k, int maxPts) {
    if (k == 0 || n >= k + maxPts - 1) {
        return 1.0;
    }
    double[] dp = new double[n + 1];
    dp[0] = 1.0;
    double windowSum = 1.0;
    double result = 0.0;

    for (int i = 1; i <= n; i++) {
        dp[i] = windowSum / maxPts;
        
        if (i < k) {
            windowSum += dp[i];
        } else {
            result += dp[i];
        }
        
        if (i >= maxPts) {
            windowSum -= dp[i - maxPts];
        }
    }
    return result;
}
```
### Algorithm
- 1. Handle edge cases (`k=0` or `n >= k + maxPts - 1`).
- 2. Initialize a `dp` array of size `n+1`. Set `dp[0] = 1.0`.
- 3. Initialize `windowSum = 1.0` (for `dp[0]`) and `result = 0.0`.
- 4. Iterate `i` from 1 to `n`.
- 5. Calculate `dp[i] = windowSum / maxPts`.
- 6. If `i < k`, add `dp[i]` to `windowSum` because it's a score from which we can continue drawing.
- 7. If `i >= k`, add `dp[i]` to `result` because it's a final score within our target range.
- 8. If `i >= maxPts`, subtract `dp[i - maxPts]` from `windowSum` as it slides out of the window of the last `maxPts` scores.
- 9. Return `result`.

# Solutions
### Java

```java
class Solution {
private
  double[] f;
private
  int n, k, maxPts;
public
  double new21Game(int n, int k, int maxPts) {
    f = new double[k];
    this.n = n;
    this.k = k;
    this.maxPts = maxPts;
    return dfs(0);
  }
private
  double dfs(int i) {
    if (i >= k) {
      return i <= n ? 1 : 0;
    }
    if (i == k - 1) {
      return Math.min(n - k + 1, maxPts) * 1.0 / maxPts;
    }
    if (f[i] != 0) {
      return f[i];
    }
    return f[i] = dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts;
  }
}

```

### CPP

```cpp
class Solution {
public:
  double new21Game(int n, int k, int maxPts) {
    vector<double> f(k);
    function<double(int)> dfs = [&](int i) -> double {
      if (i >= k) {
        return i <= n ? 1 : 0;
      }
      if (i == k - 1) {
        return min(n - k + 1, maxPts) * 1.0 / maxPts;
      }
      if (f[i]) {
        return f[i];
      }
      return f[i] = dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts;
    };
    return dfs(0);
  }
};

```

### Python

```python
class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float: @ cache def dfs(i: int) -> float: if i >= k: return int(i <= n) if i == k - 1: return min(n - k + 1, maxPts) / maxPts return dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts return dfs(0)

```