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 maxPts is an integer. Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets k or more points.

Return the probability that Alice has n or fewer points.

Answers within 10-5 of the actual answer are considered accepted.

Example

Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.

Solution

Great solution found here

/**
 * @param {number} n
 * @param {number} k
 * @param {number} maxPts
 * @return {number}
 */
var new21Game = function (n, k, maxPts) {
  // dp[i] means the probability of getting i points
  let dp = new Array(n + 1);
  //Set the base case
  dp[0] = 1;
  // s is the sum of previous k dp values
  s = k > 0 ? 1 : 0;
  for (let i = 1; i <= n; i++) {
    //dp index is equal to the sum of previous k dp values divided by maxPts
    dp[i] = s / maxPts;
    //if i is less than k, add dp[i] to s
    if (i < k) {
      s += dp[i];
    }
    //if i is greater than or equal to maxPts, subtract dp[i - maxPts] from s
    if (i - maxPts >= 0 && i - maxPts < k) {
      s -= dp[i - maxPts];
    }
  }
  let ans = 0;
  //sum all the dp values from k to n
  for (let i = k; i <= n; i++) {
    //add dp[i] to ans
    ans += dp[i];
  }
  return ans;
};