837. New 21 Game - Explanation

Description

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 <= 10,000
1 <= maxPts <= 10,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Dynamic Programming (Top-Down)

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        cache = {}

        def dfs(score):
            if score >= k:
                return 1 if score <= n else 0
            if score in cache:
                return cache[score]

            prob = 0
            for i in range(1, maxPts + 1):
                prob += dfs(score + i)

            cache[score] = prob / maxPts
            return cache[score]

        return dfs(0)

Time & Space Complexity

Time complexity: $O(k * m)$
Space complexity: $O(k)$

Where $k$ is the threshold score, $m$ is the maximum points per draw and $n$ is the upper bound on score.

2. Dynamic Programming (Top-Down Optimized)

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        cache = {}

        def dfs(score):
            if score == k - 1:
                return min(n - k + 1, maxPts) / maxPts
            if score > n:
                return 0
            if score >= k:
                return 1.0

            if score in cache:
                return cache[score]

            cache[score] = dfs(score + 1)
            cache[score] -= (dfs(score + 1 + maxPts) - dfs(score + 1)) / maxPts
            return cache[score]

        return dfs(0)

Time & Space Complexity

Time complexity: $O(k + m)$
Space complexity: $O(n)$

Where $k$ is the threshold score, $m$ is the maximum points per draw and $n$ is the upper bound on score.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp = [0] * (n + 1)
        dp[0] = 1.0

        for score in range(1, n + 1):
            for draw in range(1, maxPts + 1):
                if score - draw >= 0 and score - draw < k:
                    dp[score] += dp[score - draw] / maxPts

        return sum(dp[k:n + 1])

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $k$ is the threshold score, $m$ is the maximum points per draw and $n$ is the upper bound on score.

4. Dynamic Programming (Sliding Window)

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0:
            return 1.0

        windowSum = 0
        for i in range(k, k + maxPts):
            windowSum += 1 if i <= n else 0

        dp = {}
        for i in range(k - 1, -1, -1):
            dp[i] = windowSum / maxPts
            remove = 0
            if i + maxPts <= n:
                remove = dp.get(i + maxPts, 1)
            windowSum += dp[i] - remove
        return dp[0]

Time & Space Complexity

Time complexity: $O(k + m)$
Space complexity: $O(n)$

Where $k$ is the threshold score, $m$ is the maximum points per draw and $n$ is the upper bound on score.