#837

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

New 21 Game

Calculate the probability Alice reaches at most n points using state transition dynamic programming efficiently.

math dynamic programming sliding window probability and statistics

Problem Statement

Alice plays a card-based game starting with 0 points and draws numbers while her total is less than k. Each draw adds an integer randomly from 1 to maxPts, inclusive, with all outcomes equally likely.

She stops drawing when her total reaches k or more points. The task is to calculate the probability that Alice's final score does not exceed n, accounting for all random draw sequences.

Examples

Example 1

Input: n = 10, k = 1, maxPts = 10

Output: 1.00000

Alice gets a single card, then stops.

Example 2

Input: n = 6, k = 1, maxPts = 10

Output: 0.60000

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

Example details omitted.

Constraints

0 <= k <= n <= 104
1 <= maxPts <= 104

Solution Approach

Define DP State

Let dp[x] represent the probability that Alice reaches exactly x points. Initialize dp[0] = 1, since she starts with zero points.

Use Sliding Window Sum

Instead of summing all prior probabilities for each dp[x], maintain a running sum of the last maxPts dp values to calculate dp[x] in O(1) per step. This leverages the equal probability distribution and reduces time complexity.

Aggregate Final Probability

Sum all dp[x] for x from k to n to get the total probability of Alice finishing with at most n points. Handle k = 0 separately, where Alice stops immediately with probability 1.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) using sliding window accumulation for dp, and space complexity is O(n) to store the DP array. Without sliding window optimization, naive DP would be O(n*maxPts).

What Interviewers Usually Probe

Candidate defines dp[x] clearly and explains why each state depends on previous maxPts states.
Candidate optimizes naive DP using a sliding window to reduce time complexity.
Candidate correctly handles edge cases like k = 0 or n < k without overcounting probabilities.

Common Pitfalls or Variants

Common pitfalls

Attempting naive summation of all prior states for each dp[x], leading to TLE.
Forgetting to cap the probability sum at n, causing overestimation.
Not accounting for k = 0, which should immediately return 1.0 probability.

Follow-up variants

Change maxPts to a non-uniform probability distribution for each draw, requiring weighted DP.
Compute expected value instead of probability, altering the DP recurrence slightly.
Consider multiple players drawing sequentially, updating DP to track joint probabilities.

FAQ

What is the main DP pattern in New 21 Game?

The core pattern is state transition dynamic programming, tracking the probability of each point total and accumulating over previous maxPts states.

Why use a sliding window in this problem?

Sliding window efficiently computes dp[x] by summing the previous maxPts probabilities in O(1) per step, avoiding O(n*maxPts) computation.

How do we handle k = 0 in New 21 Game?

If k = 0, Alice draws no cards and the probability of being at most n is 1, since she stops immediately.

Can this method handle large maxPts values?

Yes, sliding window ensures that even large maxPts do not lead to excessive computation, keeping time complexity linear in n.

How do we compute the final probability?

Sum dp[x] for all x between k and n inclusive, as these represent all possible outcomes where Alice stops at or below n points.

terminal

Solution

Solution 1: Memoized Search

We design a function $dfs(i)$, which represents the probability that when the current score is $i$, the final score does not exceed $n$ when we stop drawing numbers. The answer is $dfs(0)$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        @cache
        def dfs(i: int) -> float:
            if i >= k:
                return int(i <= n)
            if i == k - 1:
                return min(n - k + 1, maxPts) / maxPts
            return dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts

        return dfs(0)

Solution 2: Dynamic Programming

We can convert the memoized search in Solution 1 into dynamic programming.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        @cache
        def dfs(i: int) -> float:
            if i >= k:
                return int(i <= n)
            if i == k - 1:
                return min(n - k + 1, maxPts) / maxPts
            return dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts

        return dfs(0)

Continue Practicing

#808 soup servings #1227 airplane seat assignment probability #1467 probability of a two boxes having the same number of distinct balls