New 21 Game Probability

A player starts with 0 points and repeatedly draws an integer uniformly at random from 1 through maxPts, inclusive. The player stops drawing as soon as the score is at least k.
Return the probability that the final score is at most n.

Function
new21Game(n: int, k: int, maxPts: int) → double

Examples
Example 1
n = 10
k = 1
maxPts = 10
return = 1.0
Every possible first draw is at most 10.
Example 2
n = 6
k = 1
maxPts = 10
return = 0.6
Exactly six of the ten equally likely first draws finish at 6 or below.
Example 3
n = 21
k = 17
maxPts = 10
return = 0.7327777870686082
Dynamic programming accumulates the probability of every reachable stopping score from 17 through 21.

Constraints
0 <= k <= n <= 10000
1 <= maxPts <= 10000
The result is accepted with absolute tolerance 1e-9.

Define dp[i] as the probability of ever reaching score i. dp[0] = 1. For any i, dp[i] is the sum of dp[j] over the previous maxPts scores j that were still drawing (j < k), divided by maxPts. Don't recompute that sum. Keep a running window sum: add dp[i] to it when i < k, and subtract dp[i - maxPts] when it falls out of range. The answer is the sum of dp[i] for i from k to n. The classic pitfall is including scores at or above k in the window, since the player has stopped there and can't draw again. Also handle k = 0 up front, where the player never draws and the answer is 1.0. Doubles are fine given the 1e-9 tolerance. If the window logic slips under pressure, StealthCoder can hand you the clean version during the live OA.

If this hits your live OA and you blank, StealthCoder solves it in seconds, invisible to the proctor.