Problem Description

The New 21 Game problem asks you to compute the probability that Alice’s score is at most n when she stops drawing numbers in a game. The game works as follows:

• Alice starts with 0 points.
• She draws numbers randomly, and each draw adds an integer between 1 and maxPts (inclusive) to her score, each with equal probability.
• She stops drawing numbers as soon as her score reaches or exceeds k.
• You are given three integers: n (the maximum score to be considered a "win"), k (the threshold at which Alice stops), and maxPts (the maximum number Alice can draw in a single turn).

The goal is to compute the probability that Alice's final score is less than or equal to n.

Constraints:

• 1 ≤ n ≤ 10⁴
• 1 ≤ k ≤ 10⁴
• 1 ≤ maxPts ≤ 10⁴

Thought Process

At first glance, this problem seems to require simulating all possible game outcomes. For each possible sequence of draws, we could track the probability of reaching every possible total score. However, as the number of possible sequences grows exponentially with k and maxPts, brute-force simulation is infeasible for large inputs.

Instead of simulating every path, we can use dynamic programming: for each possible score, we can calculate the probability of reaching that score, and then use those probabilities to compute the probabilities for higher scores. The key insight is that the probability of reaching a certain score depends only on the probabilities of reaching previous scores.

To optimize, we notice that for each score x less than k, the probability of reaching x can be expressed as the average of the probabilities of reaching the previous maxPts scores. This observation allows us to use a sliding window sum to efficiently compute probabilities for all scores up to n.

Solution Approach

We use dynamic programming to solve this problem efficiently. Let’s break down the steps:

1. Define the DP Array:
   • Let dp[x] be the probability that Alice gets a score of exactly x.
2. Base Case:
   • dp[0] = 1.0, since Alice starts at 0 with probability 1.
3. Transition:
   • If x < k, Alice can draw again. For each possible draw (1 to maxPts), the probability of reaching x + i is dp[x] / maxPts for each i.
   • We can use a sliding window sum to efficiently compute the sum of probabilities for the range [x - maxPts, x - 1].
4. Stop Condition:
   • Alice stops drawing when her score is at least k. So, for scores in the range [k, n], we sum up dp[x] to get the final answer.
5. Edge Cases:
   • If k == 0 or n >= k + maxPts - 1, Alice can always reach a score ≤ n with probability 1.0.
6. Implementation:
   • We initialize dp[0] to 1.0 and use a variable windowSum to keep track of the sum of the previous maxPts probabilities.
   • For each score x from 1 to n:
     • If x < k, update windowSum by adding dp[x] to it.
     • If x - maxPts >= 0, subtract dp[x - maxPts] from windowSum.

Example Walkthrough

Consider n = 6, k = 1, maxPts = 10.

• Alice stops immediately after her first draw (since k = 1).
• Her only possible scores are 1 through 10, each with probability 1/10.
• We want the probability that her score is ≤ 6, i.e., 1, 2, 3, 4, 5, or 6.
• So, the answer is 6/10 = 0.6.

For a more complex example, suppose n = 21, k = 17, maxPts = 10:

• We build up dp for each score from 1 to 21, using the sliding window sum of the previous maxPts probabilities.
• Once we reach x ≥ k, we stop adding to windowSum and start accumulating the answer.
• The final answer is the sum of dp[17] to dp[21].

Code Implementation

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k + maxPts - 1:
            return 1.0
        dp = [0.0] * (n + 1)
        dp[0] = 1.0
        windowSum = 1.0
        result = 0.0
        for i in range(1, n + 1):
            dp[i] = windowSum / maxPts
            if i < k:
                windowSum += dp[i]
            else:
                result += dp[i]
            if i - maxPts >= 0:
                windowSum -= dp[i - maxPts]
        return result
      

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0 || n >= k + maxPts - 1) return 1.0;
        vector<double> dp(n + 1, 0.0);
        dp[0] = 1.0;
        double windowSum = 1.0, 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 >= 0) windowSum -= dp[i - maxPts];
        }
        return result;
    }
};
      

class Solution {
    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, 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 >= 0) windowSum -= dp[i - maxPts];
        }
        return result;
    }
}
      

var new21Game = function(n, k, maxPts) {
    if (k === 0 || n >= k + maxPts - 1) return 1.0;
    let dp = new Array(n + 1).fill(0.0);
    dp[0] = 1.0;
    let windowSum = 1.0, result = 0.0;
    for (let i = 1; i <= n; i++) {
        dp[i] = windowSum / maxPts;
        if (i < k) windowSum += dp[i];
        else result += dp[i];
        if (i - maxPts >= 0) windowSum -= dp[i - maxPts];
    }
    return result;
};
      

Time and Space Complexity

Brute-force: The naive approach would try to simulate every possible sequence of draws, which would take O(maxPts^k) time and space—utterly infeasible for large values.

Optimized (Dynamic Programming):

• Time Complexity: O(n), since we compute dp[i] for each i from 1 to n, and each computation is O(1) using the sliding window.
• Space Complexity: O(n), as we store dp up to n.

This is efficient enough for the given constraints (n up to 10⁴).

Summary

The New 21 Game problem is a classic example of using dynamic programming to efficiently compute probabilities in a stochastic process. By recognizing that each state depends only on a fixed window of previous states, we avoid brute-force enumeration and achieve a linear-time solution. The sliding window technique for the DP transition is the key insight, making the approach both elegant and efficient.