{x}
blog image

New 21 Game

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 <= 104
  • 1 <= maxPts <= 104

Solution Explanation for LeetCode 837: New 21 Game

This problem involves calculating the probability that Alice's score will be less than or equal to n after playing a simplified version of the card game 21. We can solve this using dynamic programming or a mathematical approach. The dynamic programming approach is explained below.

Approach: Dynamic Programming

The core idea is to build a DP array where dp[i] represents the probability that Alice's score is less than or equal to n given that her current score is i.

  1. Base Cases:

    • If i >= k, Alice stops drawing. The probability is 1 if i <= n, otherwise 0.
    • If i == k - 1, Alice draws one more card. The probability of ending with a score less than or equal to n is the number of favorable outcomes (scores between k and n, inclusive) divided by the total number of possible outcomes (maxPts).

  2. Recursive Relation: For i < k - 1, Alice draws a card. The next score will be between i + 1 and i + maxPts, each with equal probability (1/maxPts). The probability of ending with a score less than or equal to n starting from score i is the average of the probabilities starting from scores i + 1, i + 2, ..., i + maxPts. This can be expressed recursively:

    dp[i] = (dp[i+1] + dp[i+2] + ... + dp[i + maxPts]) / maxPts

  3. Optimization: The recursive relation can be optimized using the following transformation:

    dp[i] = (sum(dp[i+1] to dp[i+maxPts])) / maxPts

    maxPts * dp[i] = sum(dp[i+1] to dp[i+maxPts])

    dp[i] = (sum(dp[i+1] to dp[i+maxPts])) / maxPts maxPts * dp[i] = sum(dp[i+1] to dp[i+maxPts]) We also know that maxPts * dp[i+1] = sum(dp[i+2] to dp[i+maxPts+1]). Thus, subtracting the second equation from the first one, we obtain: maxPts * (dp[i] - dp[i+1]) = dp[i+1] - dp[i+maxPts+1] dp[i] = dp[i+1] + (dp[i+1] - dp[i+maxPts+1]) / maxPts

This iterative approach avoids redundant calculations, making it much more efficient than the naive recursive solution.

Time and Space Complexity Analysis

  • Time Complexity: O(k * maxPts) in the worst case because the iterative approach involves a single loop from k-2 down to 0. The overall complexity is dominated by this loop. In practice, it's often less than O(k * maxPts) because the loop stops early in many cases.

  • Space Complexity: O(k + maxPts) due to the size of the DP array f.

Code Examples (Python)

The provided code implements the optimized iterative dynamic programming solution:

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        f = [0] * (k + maxPts)
        for i in range(k, min(n + 1, k + maxPts)):
            f[i] = 1
        f[k - 1] = min(n - k + 1, maxPts) / maxPts
        for i in range(k - 2, -1, -1):
            f[i] = f[i + 1] + (f[i + 1] - f[i + maxPts + 1]) / maxPts
        return f[0]

This code efficiently computes the probability, leveraging the optimized dynamic programming approach to avoid redundant calculations. The other languages provided follow a similar structure and logic.