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, W], where W is an integer. Each draw is independent and the outcomes have equal probabilities.
Alice stops drawing numbers when she gets K or more points. What is the probability that she has N or less points?
Example 1:
Input: N = 10, K = 1, W = 10 Output: 1.00000 Explanation: Alice gets a single card, then stops.
Example 2:
Input: N = 6, K = 1, W = 10 Output: 0.60000 Explanation: Alice gets a single card, then stops. In 6 out of W = 10 possibilities, she is at or below N = 6 points.
Example 3:
Input: N = 21, K = 17, W = 10 Output: 0.73278
Note:
0 <= K <= N <= 100001 <= W <= 10000- Answers will be accepted as correct if they are within
10^-5of the correct answer. - The judging time limit has been reduced for this question.
function new21Game(n: number, k: number, maxPts: number): number {
if (!k) return 1.0;
let dp = new Array(k + maxPts).fill(0.0);
for (let i = k; i <= n && i < k + maxPts; i++) {
dp[i] = 1.0;
}
dp[k - 1] = 1.0 * Math.min(n - k + 1, maxPts) / maxPts;
for (let i = k - 2; i >= 0; i--) {
dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
}
return dp[0];
};