New 21 Game

How it works

We can optimize the bottom-up approach using a sliding window. Notice that dp[i] depends on the sum of dp values from dp[i-maxPts] to dp[i-1], but only those in the range [0, k-1]. Instead of recomputing this sum each time, we maintain a running window sum.

Working backwards from k-1 to 0, we compute dp[i] as windowSum / maxPts. The window initially covers scores from k to k+maxPts-1. For scores >= k and <= n, the probability of success is 1 (we already stopped and the score is valid). As we move the window, we add the newly computed dp value and remove the value that slides out.

Steps

1. If k is 0, return 1.0 (already done, score 0 is valid).
2. Initialize windowSum as the count of scores from k to k+maxPts-1 that are <= n.
3. Iterate from k-1 down to 0:
   • Set dp[i] = windowSum / maxPts.
   • Update windowSum: add dp[i] and subtract the value sliding out of the window (if it exists and is <= n).
4. Return dp[0].

Complexity

• Time complexity: O(k + m)
• Space complexity: O(n)

Where k is the threshold score, m is the maximum points per draw and n is the upper bound on score.

Things to watch for

Missing Edge Case When k is Zero

When k equals 0, Alice never draws any cards and stays at score 0, which is always less than or equal to n. The probability is exactly 1.0 in this case. Failing to handle this edge case leads to division by zero or incorrect recursion that never terminates.

Incorrect Probability for Terminal States

When the score is at least k, Alice stops drawing. The probability of success is 1 if the score is also at most n, and 0 otherwise. Some solutions incorrectly return 1 for all scores >= k, forgetting that scores above n are losing outcomes.

Floating Point Precision in Window Sum

The sliding window optimization maintains a running sum of probabilities. Accumulated floating point errors from many additions and subtractions can cause the final probability to slightly exceed 1 or become negative. While typically not causing wrong answers on test cases, this can be addressed by clamping results to [0, 1].

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

        windowSum = 0
        for i in range(k, k + maxPts):
            windowSum += 1 if i <= n else 0

        dp = {}
        for i in range(k - 1, -1, -1):
            dp[i] = windowSum / maxPts
            remove = 0
            if i + maxPts <= n:
                remove = dp.get(i + maxPts, 1)
            windowSum += dp[i] - remove
        return dp[0]

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (k == 0) {
            return 1.0;
        }
        double windowSum = 0.0;
        for (int i = k; i < k + maxPts; i++) {
            windowSum += (i <= n) ? 1.0 : 0.0;
        }
        unordered_map<int, double> dp;
        for (int i = k - 1; i >= 0; i--) {
            dp[i] = windowSum / maxPts;
            double remove = 0.0;
            if (i + maxPts <= n) {
                remove = (dp.find(i + maxPts) != dp.end()) ? dp[i + maxPts] : 1.0;
            }
            windowSum += dp[i] - remove;
        }
        return dp[0];
    }
};