Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

From a score below k, the chance of finishing within n is the average of the chances from the next maxPts scores. Once the score reaches k, drawing stops, so the probability is simply one or zero according to whether the final score is allowed. Adjacent averages overlap almost completely, enabling a sliding sum.

Approach

Return one immediately for the reference implementation's guaranteed-success cases, including k == 0.
Define dp[i] as the chance of success starting from score i. Initialize terminal scores from k through k + maxPts - 1 to one when at most n, otherwise zero.
Sum those terminal probabilities. Work backward from k - 1 to zero, assigning dp[i] = windowSum / maxPts.
Add dp[i] and remove dp[i + maxPts] to prepare the next overlapping window. Return dp[0], the probability from the actual starting score.

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

        dp = [0] * (k + maxPts)
        # dp[i] = prob to win (points <= n) from i scor
        wsum = 0

        for i in range(k, k + maxPts):
            if i <= n:
                dp[i] = 1
                wsum += 1

        for i in range(k - 1, -1, -1):
            dp[i] = wsum / maxPts
            wsum += dp[i] - dp[i + maxPts]

        return dp[0]

Complexity analysis

Let K = k and W = maxPts. Initializing the terminal states and filling the sliding DP window takes O(K + W) time and the DP array uses O(K + W) auxiliary space. The early-return cases use O(1).