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
- Let
dp[i]be the probability of reaching exactly scoreiwhile still belowk. - From any score below
kyou continue drawing, sodp[i] = (dp[i-1] + ... + dp[i-maxPts]) / maxPts, where only terms belowkare included. - A sliding window sum of the last
maxPtsprobabilities gives O(n) total. - The answer is the sum of
dp[i]foriin[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 reachesk, so only states belowkenter the window. - Missing the early exit
n >= k + maxPts: the maximum reachable score isk + maxPts - 1, so the probability is 1. - Summing
dp[0..n]: only final scores>= kcount, so the sum runs overdp[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.