New 21 Game

medium math dp sliding window probability

Problem

Alice starts with 0 points and draws integers uniformly from [1, maxPts]. She keeps drawing while her total is strictly less than k. Return the probability her final total is ≤ n.

Inputn = 10, k = 1, maxPts = 10

Output1.00000

Alice draws once; every outcome 1..10 ≤ 10.

maxPts

def new21Game(n, k, maxPts):
    if k == 0 or n >= k + maxPts:
        return 1.0
    dp = [0.0] * (n + 1)
    dp[0] = 1.0
    window = 1.0
    ans = 0.0
    for i in range(1, n + 1):
        dp[i] = window / maxPts
        if i < k:
            window += dp[i]
        else:
            ans += dp[i]
        if i - maxPts >= 0 and i - maxPts < k:
            window -= dp[i - maxPts]
    return ans

function new21Game(n, k, maxPts) {
  if (k === 0 || n >= k + maxPts) return 1.0;
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1.0;
  let window = 1.0, ans = 0.0;
  for (let i = 1; i <= n; i++) {
    dp[i] = window / maxPts;
    if (i < k) window += dp[i];
    else ans += dp[i];
    if (i - maxPts >= 0 && i - maxPts < k) window -= dp[i - maxPts];
  }
  return ans;
}

class Solution {
    public double new21Game(int n, int k, int maxPts) {
        if (k == 0 || n >= k + maxPts) return 1.0;
        double[] dp = new double[n + 1];
        dp[0] = 1.0;
        double window = 1.0, ans = 0.0;
        for (int i = 1; i <= n; i++) {
            dp[i] = window / maxPts;
            if (i < k) window += dp[i];
            else ans += dp[i];
            if (i - maxPts >= 0 && i - maxPts < k) window -= dp[i - maxPts];
        }
        return ans;
    }
}

double new21Game(int n, int k, int maxPts) {
    if (k == 0 || n >= k + maxPts) return 1.0;
    vector<double> dp(n + 1, 0.0);
    dp[0] = 1.0;
    double window = 1.0, ans = 0.0;
    for (int i = 1; i <= n; i++) {
        dp[i] = window / maxPts;
        if (i < k) window += dp[i];
        else ans += dp[i];
        if (i - maxPts >= 0 && i - maxPts < k) window -= dp[i - maxPts];
    }
    return ans;
}

Explanation

Alice keeps drawing cards while her score is below k, each draw adding a uniformly random number from 1 to maxPts. We want the chance her final score is at most n. The key idea is to compute dp[i] = the probability of landing exactly on score i, then add up the probabilities of all the valid stopping scores.

How can you reach score i? Only by being at some score in the range [i - maxPts, i - 1] that was still below k (so Alice was allowed to draw), and then drawing the right card. Each such source contributes dp[source] / maxPts, so dp[i] is the sum of those divided by maxPts.

Instead of re-summing that range every time, we keep a sliding window total of the eligible dp values. When i < k Alice can still draw from here, so we add dp[i] into the window; once i >= k she stops, so that probability goes into the ans instead. As the window moves past i - maxPts we subtract that old value out.

There is also an instant shortcut: if k == 0 or n >= k + maxPts, every outcome is <= n, so the answer is simply 1.0.

Example: with n = 10, k = 1, maxPts = 10, Alice draws once and any result 1..10 is <= 10, so the probability is 1.00000. The sliding window keeps the whole computation linear in n.

Time: O(n) Space: O(n)