New 21 Game

Problem Description

Alice plays a game where she starts with 0 points and draws numbers from a range of [1, maxPts] until her points reach or exceed k. The task is to find the probability that Alice has n or fewer points after she stops drawing.

Key Insights

• Alice draws points randomly and independently from a uniform distribution between 1 and maxPts.
• The game ends when Alice's points reach or exceed k, hence she may not always reach exactly n points.
• The probability can be computed using dynamic programming or sliding window techniques to track the possible scores.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use dynamic programming to keep track of the probabilities of reaching each score from 0 to n. We define a probability array dp where dp[i] represents the probability of having exactly i points.

1. Initialize dp[0] = 1, since Alice starts with 0 points.
2. For each point total from 1 to n, calculate the probability of reaching that score based on the previous scores (from i - maxPts to i - 1).
3. Use a sliding window to efficiently sum the probabilities of the last maxPts scores to update the current score's probability.
4. Finally, sum the probabilities from dp[0] to dp[n] to get the total probability of having n or fewer points.

Code Solutions