New 21 Game

MediumProbability DP · Sliding Window🧩 Probability DP LeetCode #837 ↗Updated Oct 30, 2026

Problem

Alice starts with 0 points. While her total is below k, she draws a random integer from 1 to maxPts (uniformly, independently) and adds it. She stops as soon as her total reaches k or more. Return the probability that her final total is ≤ n.

Inputn = 10, k = 1, maxPts = 10Output1.00000

Inputn = 6, k = 1, maxPts = 10Output0.60000

Inputn = 21, k = 17, maxPts = 10Output0.73278

0 ≤ k ≤ n ≤ 10⁴ · 1 ≤ maxPts ≤ 10⁴ · answers within 10^-5 are accepted

Try it yourself

Java

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Let dp[x] be the chance of ever standing on exactly x points. It is (1/maxPts) × the sum of dp[j] over the previous maxPts totals j that were still < k (Alice only draws from those). That sum is a sliding window, so each dp[x] costs O(1).

PatternProbability DP

Instinct Asked for a probability or expected value after random moves? Run DP over (step, state) and split each state's mass across every outcome.

Memory hack Pour the probability like water - split it across the moves, let what spills off the board drain away, and the puddle that's left is your answer.

Open the Probability DP guide →

Approaches

Brute ForceRecursive Game Simulation

Time O(maxPts^k)Space O(k)

win(p) = 1 or 0 once p ≥ k (depending on p ≤ n); otherwise the average of win(p + d) for every draw d. It enumerates every possible sequence of draws.

Java

public double new21Game(int n, int k, int maxPts) {
    return win(0, n, k, maxPts);
}

private double win(int pts, int n, int k, int maxPts) {
    if (pts >= k) return pts <= n ? 1.0 : 0.0; // game over
    double sum = 0;
    for (int d = 1; d <= maxPts; d++) sum += win(pts + d, n, k, maxPts);
    return sum / maxPts;
}

A direct translation of the rules, only usable for tiny k.

BetterForward DP, Summing Each Window

Time O(n · maxPts)Space O(n)

Compute dp[x] for x = 1..n by looping over every predecessor j in [x-maxPts, x-1] with j < k. The answer is dp[k] + … + dp[n]: each stopping total is reached at most once, so these events are disjoint.

Java

public double new21Game(int n, int k, int maxPts) {
    if (k == 0) return 1.0; // no draws at all
    double[] dp = new double[n + 1];
    dp[0] = 1.0;
    double answer = 0;
    for (int x = 1; x <= n; x++) {
        double sum = 0;
        int from = Math.max(0, x - maxPts), to = Math.min(x - 1, k - 1);
        for (int j = from; j <= to; j++) sum += dp[j]; // still drawing at j
        dp[x] = sum / maxPts;
        if (x >= k) answer += dp[x];
    }
    return answer;
}

Polynomial, but 10⁴ × 10⁴ = 10⁸ operations is borderline.

OptimalSliding-Window DP

Time O(n)Space O(n)

Keep window = sum of dp[j] for the last maxPts totals that are below k. After computing dp[x], add it to the window only if x < k, and drop dp[x - maxPts] as it slides out. Early exit: if n ≥ k - 1 + maxPts, even the worst final total fits, so return 1.

Java

public double new21Game(int n, int k, int maxPts) {
    if (k == 0 || n >= k - 1 + maxPts) return 1.0; // can never exceed n
    double[] dp = new double[n + 1];
    dp[0] = 1.0;
    double window = 1.0, answer = 0;
    for (int x = 1; x <= n; x++) {
        dp[x] = window / maxPts;
        if (x < k) window += dp[x];   // Alice keeps drawing from x
        else answer += dp[x];         // Alice stops at x (and x <= n)
        int out = x - maxPts;         // leaves the window for x + 1
        if (out >= 0 && out < k) window -= dp[out];
    }
    return answer;
}

Dry runn = 10, k = 1, maxPts = 10

x current total changed

init
1
x
·

·

n=2,k=2,max=2; w=1
x=1
1

.5
x
·

1/2 < k: w=1.5
x=2
1

.5

.75
x
1.5/2: ans=.75
slide
1

.5

.75

drop dp[0]: w=.5

Linear time — the intended solution.

Pro tip

The early-exit check is also what makes the example (10, 1, 10) return 1 immediately — mention it before coding the loop.

At a glance

Level	Approach	Time	Space
Brute Force	Recursive Game Simulation	`O(maxPts^k)`	`O(k)`
Better	Forward DP, Summing Each Window	`O(n · maxPts)`	`O(n)`
Optimal	Sliding-Window DP	`O(n)`	`O(n)`

Common pitfalls

Adding dp[x] to the window when x ≥ k — Alice stopped there.
Forgetting k == 0: she never draws, so the answer is 1.
Subtracting dp[x - maxPts] even when that index was ≥ k (never added).

Interview tips

Define the DP state in words: “probability we ever hold exactly x points”.
Show the O(n·maxPts) version first, then spot the repeated window sum.
Explain why summing dp[k..n] is valid: stop events are mutually exclusive.

Pattern

Probability DP + sliding window sum → each state averages a fixed-width range of earlier states.

My notes saved in this browser