New 21 Game: Sliding Window DP Explained

Alice plays a game where she starts at 0 points and draws cards until her score reaches k or more. Each draw adds a random number from 1 to maxPts, with equal probability. You need to find the probability that her final score is at most n. This is LeetCode 837: New 21 Game, rated medium. It looks like a simple probability question, but the key challenge is computing it efficiently without blowing up your time complexity.

The problem

Given three integers n, k, and maxPts, Alice starts with 0 points and repeatedly draws a number uniformly at random from [1, maxPts]. She stops drawing when her score is k or more. Return the probability that her score is at most n.

Input: n = 6, k = 1, maxPts = 10
Output: 0.6
# Alice draws one card (since k=1, she stops after any draw).
# She gets 1..10 each with probability 0.1.
# P(score <= 6) = 6 * 0.1 = 0.6

The key insight: DP with a sliding window

Define dp[i] as the probability of reaching exactly score i. The base case is dp[0] = 1, because Alice starts at 0 with certainty.

For each score i from 1 upward, Alice could have arrived from any score j where j is in the range [i - maxPts, i - 1], but only if j < k (because she would have stopped drawing at j if j >= k). Each transition has probability 1 / maxPts, so:

dp[i] = sum(dp[j] for j in [i - maxPts, i - 1] if j < k) / maxPts

Naively computing that sum for each i takes O(maxPts) per cell, giving O(n * maxPts) overall. But notice that the sum is over a sliding window of at most maxPts consecutive entries. If you maintain a running sum and add/remove entries as the window slides, each cell takes O(1).

The trick is that you add dp[i] to the running sum only when i < k (because states at or above k are terminal and do not contribute to future transitions). And you subtract dp[i - maxPts] from the running sum when it falls out of the window.

Step-by-step walkthrough

Let's trace through a concrete example with n = 6, k = 3, maxPts = 3. Alice draws while her score is below 3, adding 1, 2, or 3 each time with equal probability (1/3 each).

After filling the table, the answer is the sum of dp[k] through dp[n], which captures every stopping score that is at most n. In this example that is dp[3] + dp[4] + dp[5] = 0.593 + 0.309 + 0.300 = 0.600 (approximately). Notice how the window sum shrinks as entries leave the window and as entries at or above k do not get added.

The code

def new21Game(n, k, maxPts):
    if k == 0 or n >= k + maxPts - 1:
        return 1.0

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

    for i in range(1, n + 1):
        dp[i] = window_sum / maxPts
        if i < k:
            window_sum += dp[i]
        if i >= maxPts:
            window_sum -= dp[i - maxPts]

    return sum(dp[k:n + 1])

Here is what each part does.

The early return handles two trivial cases. If k is 0, Alice never draws, so her score is 0 which is always at most n. If n >= k + maxPts - 1, then even the highest possible stopping score (k - 1 + maxPts) is at most n, so the answer is 1.0.

dp[0] = 1.0 sets the base case. window_sum tracks the sum of active dp values in the current sliding window.

dp[i] = window_sum / maxPts computes the probability of landing on score i by averaging over all states that could transition here.

if i < k adds dp[i] to the window sum, because only states below k are non-terminal and can lead to further draws.

if i >= maxPts removes the element sliding out of the window. The window covers at most maxPts entries behind the current position.

Finally, sum(dp[k:n+1]) adds up all stopping probabilities from score k to score n.

Complexity analysis

Time: O(n). We iterate once from 1 to n, doing O(1) work per step thanks to the sliding window.

Space: O(n). We store the dp array of length n + 1.

The building blocks

Sliding window over a DP array

The core reusable pattern here is maintaining a running sum over a fixed-width window as you fill a DP array left to right. Instead of recomputing a sum of maxPts elements for each cell, you update the sum incrementally.

window_sum = initial_value
for i in range(1, n + 1):
    dp[i] = window_sum / maxPts
    if should_add(i):
        window_sum += dp[i]
    if i >= window_size:
        window_sum -= dp[i - window_size]

This same pattern appears whenever your DP transition involves summing over a contiguous range of previous states. The "should_add" condition is problem-specific. In the New 21 Game, it is i < k because terminal states do not feed into future transitions.

Edge cases

• k equals 0: Alice never draws. Her score is 0, which is always at most n. Return 1.0.
• n is very large (n >= k + maxPts - 1): every possible stopping score falls within bounds. Return 1.0.
• maxPts equals 1: Alice draws exactly k times, always scoring exactly k. Return 1.0 if k <= n, else 0.0.
• k equals 1: Alice draws exactly once. The answer is min(n, maxPts) / maxPts.
• n equals k minus 1: Alice must stop at exactly k or higher, so n < k means the answer is 0.0. But this is handled naturally since dp[k:n+1] would be empty.

From understanding to recall

Probability DP problems like New 21 Game combine two skills: setting up the recurrence correctly and recognizing the sliding window optimization. The recurrence itself is not too difficult once you frame it as "the probability of reaching score i depends on the probabilities of the states that could transition to i." The harder part is remembering the window management details, especially the condition for when to add vs. skip an entry.

Spaced repetition is particularly effective here because the sliding window DP pattern recurs across many problems, but the conditions change each time. By revisiting this problem at increasing intervals, you internalize not just the generic pattern but also the specific "only add if below the threshold" rule that makes New 21 Game unique.

If you can write this solution from scratch without looking at notes, you will also find yourself better equipped for problems like minimum cost tickets, longest turbulent subarray, and other DP problems where a sliding window trims the transition cost from O(w) to O(1).

Related posts

• Climbing Stairs - The simplest linear DP, same idea of building up probabilities from smaller subproblems
• Coin Change - Another DP where each state depends on a variable set of previous states
• House Robber - Linear DP with a constraint on which previous states you can use

CodeBricks groups problems like these by their underlying building blocks. Instead of grinding random problems, you drill the sliding window DP pattern until it sticks, then move on to the next pattern. That way each new problem feels like a variation on something you already know.