Alice plays the following game, loosely based on the card game "21". Alice starts with 0 points and draws numbers while she has less than k points. During each draw, she gains an integer number of points randomly from the range [1, maxPts], where ma

new21Game.js

/**
 * @param {number} n
 * @param {number} k
 * @param {number} maxPts
 * @return {number}
 */
var new21Game = function(n, k, maxPts) {
    // Edge case: if k == 0, Alice doesn't draw any cards, so score is 0 (always < n)
    // Or if n >= k + maxPts, Alice can reach any score < n with certainty
    if (k === 0 || n >= k + maxPts) return 1;

    const dp = new Array(n + 1).fill(0); // dp[i] = probability of reaching score i
    dp[0] = 1; // Base case: probability of starting at score 0 is 1

    let windowSum = 1;  // Sum of probabilities in the slinding window
    let result = 0;     // Final result: sum of probabilities for scores > k and < n

    for (let i = 1; i <= n; i++) {
        // Probability of reaching score i is average of previous maxPts scores
        dp[i] = windowSum / maxPts;

        // If score is still less than k, we can continue drawing
        if (i < k) {
            windowSum += dp[i];
        } else {
            // If score > k, we stop drawing and add to result
            result += dp[i];
        }

        // Maintain sliding window: remove dp[i - maxPts] if it's out of range
        if (i - maxPts >= 0) {
            windowSum -= dp[i - maxPts];
        }
    }

    return result;
};