⚡Flashcard Drill➔
NeetCode #690LC-837Medium1-D Dynamic Programming
← Back to All Problems

#690 · #837 · New 21 Game(新 21 点)

📌 Problem Statement & Constraints

Starting with 0 points, repeatedly draw an integer uniformly from [1, maxPts] and add it, stopping as soon as the score reaches k or more. Return the probability that the final score is at most n. Constraints: 0 <= k <= n <= 10^4, 1 <= maxPts <= 10^4.

💡 Core Algorithmic Approaches

  1. Let dp[i] be the probability of reaching exactly score i while still below k.
  2. From any score below k you continue drawing, so dp[i] = (dp[i-1] + ... + dp[i-maxPts]) / maxPts, where only terms below k are included.
  3. A sliding window sum of the last maxPts probabilities gives O(n) total.
  4. The answer is the sum of dp[i] for i in [k, n].

💻 Benchmark Python3 Implementation

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k + maxPts:
            return 1.0                 # the score can never exceed n
        dp = [0.0] * (n + 1)
        dp[0] = 1.0
        window = 1.0                   # sum of dp over the last maxPts positions below k
        for i in range(1, n + 1):
            dp[i] = window / maxPts
            if i < k:
                window += dp[i]        # only scores below k keep drawing
            if i - maxPts >= 0 and i - maxPts < k:
                window -= dp[i - maxPts]
        return sum(dp[k:n + 1])

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with a sliding window.
💾 Space Complexity
O(n): the DP array.

⚠️ Interview Pitfalls & Follow-ups

  • Continuing to draw at or above k: the process stops once the score reaches k, so only states below k enter the window.
  • Missing the early exit n >= k + maxPts: the maximum reachable score is k + maxPts - 1, so the probability is 1.
  • Summing dp[0..n]: only final scores >= k count, so the sum runs over dp[k..n].
  • Computing the window with a nested loop: that is O(n * maxPts) and times out.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems