Watch 10 video solutions for New 21 Game, a medium level problem involving Math, Dynamic Programming, Sliding Window. This walkthrough by NeetCodeIO has 20,922 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1041 <= maxPts <= 104Problem Overview: Alice draws numbers between 1 and maxPts until her score reaches at least k. The task is to compute the probability that her final score is less than or equal to n. Each draw is equally likely, so the problem becomes a probability DP where each state depends on the previous maxPts states.
Approach 1: Dynamic Programming (Brute Transition) (Time: O(n * maxPts), Space: O(n))
Define dp[i] as the probability that Alice reaches exactly i points. Start with dp[0] = 1. For each score i, distribute its probability to the next maxPts states because Alice can draw any value from 1 to maxPts. In practice, compute dp[i] by summing probabilities from the previous maxPts states and dividing by maxPts. Once the score reaches k, Alice stops drawing, so those states contribute directly to the final probability if i ≤ n. This method is straightforward but inefficient because every state recomputes a sum over up to maxPts previous probabilities.
Approach 2: Dynamic Programming with Sliding Window (Time: O(n), Space: O(n))
The transition in the naive DP repeatedly sums the same range of probabilities. Replace that repeated summation with a sliding window. Maintain a running window sum of the previous maxPts probabilities that can still draw cards (scores less than k). Compute dp[i] = windowSum / maxPts. If i < k, add dp[i] into the window because Alice can keep drawing from that score. If i - maxPts was previously part of the window, subtract it to maintain the correct range. This converts the expensive repeated summation into constant-time updates while iterating once through the states. The final answer is the sum of dp[i] for all i from k to n.
This technique is a classic combination of dynamic programming and a sliding window optimization applied to a probability process. The DP models the probability of reaching each score, while the window tracks the active range of states that can still transition forward. Understanding this transition compression is common in interview problems involving probability and stochastic processes.
Recommended for interviews: The dynamic programming with sliding window approach. The naive DP shows you understand the probabilistic recurrence, but interviewers expect the O(n) optimization that avoids recomputing range sums. Implementing the sliding window correctly demonstrates strong DP intuition and attention to transition efficiency.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Naive Transitions) | O(n * maxPts) | O(n) | Useful for understanding the probability recurrence and deriving the state transition. |
| Dynamic Programming with Sliding Window | O(n) | O(n) | Optimal solution for interviews and production. Avoids repeated range summations. |