# 837. New 21 Game

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:

1. `0 <= K <= N <= 10000`
2. `1 <= W <= 10000`
3. Answers will be accepted as correct if they are within `10^-5` of the correct answer.
4. The judging time limit has been reduced for this question.

P(x) = 1/W * (P(x-1) + P(x-2) + P(x-W))

= 1/W * sumP(x-W, x-1)

P(A | B) = P(AB) / P(B)

P(<=N | >=K) = P(<=N && >=K) / P(>=K)

P(<=N && >=K) = P(K) + P(K+1) + … + P(N) = sumP(K, N)

P(>=K) = sumP(K, +∞) = sumP(K, K+W-1)

P[7] = 1/W * (P[6] + p[5] + … + P[1] + P[0]) = 1/W * sum[6]

P[i] = 1/W * sum[i-1]

sum[i] = sum[i-1] + P[i] = sum[i-1] + sum[i-1] / W     (when i <= W)

P[15] = 1/W * (P[14] + P[13] + … + P[5]) = 1/W * (sum[14] - sum[4])

P[i] = 1/W * (sum[i-1] - sum[i-W-1])

sum[i] = sum[i-1] + P[i] = sum[i-1] + (sum[i-1] - sum[i-W-1]) / W     (when i > W)

P[i] = 1/W * sum[i-1]     (when i <= K && i <= W)

P[i] = 1/W * (sum[i-1] - sum[i-W-1])    (when i <= K && i > W)

P[20] = 1/W * (P[16] + P[15] + P[14] + … + P[10]) = 1/W * (sum[16] - sum[9])

P[i] = 1/W * sum[K-1]     (when i > K && i <= W)

P[i] = 1/W * (sum[K-1] - sum[i-W-1])    (when i > K && i > W)

``````class Solution {
public:
double new21Game(int N, int K, int W) {
if (K == 0 || N >= K + W) return 1.0;
vector<double> sum(K + W);
sum[0] = 1.0;
for (int i = 1; i < K + W; ++i) {
int t = min(i - 1, K - 1);
if (i <= W) sum[i] = sum[i - 1] + sum[t] / W;
else sum[i] = sum[i - 1] + (sum[t] - sum[i - W - 1]) / W;
}
return (sum[N] - sum[K - 1]) / (sum[K + W - 1] - sum[K - 1]);
}
};
``````

P(<=N | >=K) = P(<=N && >=K) / P(>=K)

``````class Solution {
public:
double new21Game(int N, int K, int W) {
if (K == 0 || N >= K + W) return 1.0;
vector<double> dp(K + W);
dp[0] = 1.0;
for (int i = 1; i < K + W; ++i) {
dp[i] = dp[i - 1];
if (i <= W) dp[i] += dp[i - 1] / W;
else dp[i] += (dp[i - 1] - dp[i - W - 1]) / W;
if (i > K) dp[i] -= (dp[i - 1] - dp[K - 1]) / W;
}
return dp[N] - dp[K - 1];
}
};
``````

``````class Solution {
public:
double new21Game(int N, int K, int W) {
if (K == 0 || N >= K + W) return 1.0;
vector<double> dp(N + 1);
dp[0] = 1.0;
double sumW = 1.0, res = 0.0;
for (int i = 1; i <= N; ++i) {
dp[i] = sumW / W;
if (i < K) sumW += dp[i];
else res += dp[i];
if (i - W >= 0) sumW -= dp[i - W];
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/837

https://leetcode.com/problems/new-21-game/

https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP-O(N)

https://leetcode.com/problems/new-21-game/discuss/132478/C%2B%2B-12ms-O(K%2BW)-solution-with-explanation

https://leetcode.com/problems/new-21-game/discuss/132358/Java-O(K-%2B-W)-DP-solution-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation