New 21 Game Problem
Description
LeetCode Problem 837.
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 1:
1
2
3
Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.
Example 2:
1
2
3
4
Input: n = 6, k = 1, maxPts = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.
Example 3:
1
2
Input: n = 21, k = 17, maxPts = 10
Output: 0.73278
Constraints:
- 0 <= k <= n <= 10^4
- 1 <= maxPts <= 10^4
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
// From the initial state 0, we have 1/W probability jumping to each state between 1 and W.
// If W >= K, then W-K+1 of these states are terminal (>=K), and min(W,N)-K+1 of them
// lie between K and N, yielding a probability of (min(W,N)-K+1)/W.
// For any of remaining states i that is between 1 and K-1, we consider its probability of
// being <= N when first reaching a state that is >=K. But that is same as the probability
// of being <= N-i when first reaching a state that is >=K-i, which is new21Game(N-i,K-i,W).
// Build an array dp such that dp[i] == new21Game(N-K+i+1, i+1, W),
// so that dp[K-1] == new21Game(N,K,W). dp[i] can be computed from dp[i-1], ..., dp[i-W].
// If W>=K, new21Game(N,K,W)=(sum(new21Game(N-i,K-i,W)+min(N,W)-K+1) for i=1 to K-1)/W
// If W<K, new21Game(N,K,W)=(sum(new21Game(N-i,K-i,W) for i=1 to K-1)/W
double new21Game(int N, int K, int W) {
if (K == 0)
return 1.0;
vector<double> dp(K);
auto total = 0.0;
for (auto i = 0; i < K; ++i) {
if (i < W)
dp[i] = (total + min(N - K + 1, W - i)) / W;
else
dp[i] = total / W, total -= dp[i-W];
total += dp[i];
}
return dp[K-1];
}
};