New 21 Game — LeetCode 837 Python Solution

The problem

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.

Example

Input

n = 10, k = 1, maxPts = 10

Output

1.00000

Explanation

Alice gets a single card, then stops.

Python solution

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)

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 837. New 21 Game is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems