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.

#### Solution: Dynamic Programming

Intuition

It is clear that the probability that Alice wins the game is only related to how many points x she starts the next draw with, so we can try to formulate an answer in terms of x.

Algorithm

Let f(x) be the answer when we already have x points. When she has between K and N points, then she stops drawing and wins. If she has more than N points, then she loses.

The key recursion is . This is because there is a probability of ​ to draw each card from  to .

With this recursion, we could do a naive dynamic programming solution as follows:

// psuedocode
dp[k] = 1.0 when K <= k <= N, else 0.0
// dp[x] = the answer when Alice has x points
for k from K-1 to 0:
dp[k] = (dp[k+1] + ... + dp[k+W]) / W
return dp[0]


This leads to a solution with  time complexity, which isn’t efficient enough. Every calculation of dp[k] does  work, but the work is quite similar.

Actually, the difference is . This allows us to calculate subsequent ‘s in O(1)O(1) time, by maintaining the numerator .

As we calculate each dp[k] = , we maintain the correct value of this numerator .

class Solution {
public double new21Game(int N, int K, int W) {
double[] dp = new double[N + W + 1];
// dp[x] = the answer when Alice has x points
for (int k = K; k <= N; ++k)
dp[k] = 1.0;

double S = Math.min(N - K + 1, W);
// S = dp[k+1] + dp[k+2] + ... + dp[k+W]
for (int k = K - 1; k >= 0; --k) {
dp[k] = S / W;
S += dp[k] - dp[k + W];
}
return dp[0];
}
}
class Solution(object):
def new21Game(self, N, K, W):
dp = [0.0] * (N + W + 1)
# dp[x] = the answer when Alice has x points
for k in xrange(K, N + 1):
dp[k] = 1.0

S = min(N - K + 1, W)
# S = dp[k+1] + dp[k+2] + ... + dp[k+W]
for k in xrange(K - 1, -1, -1):
dp[k] = S / float(W)
S += dp[k] - dp[k + W]

return dp[0]

Complexity Analysis

• Time and Space Complexity: .
Note that we can reduce the time complexity to  and the space complexity to  by only keeping track of the last  values of dp, but it isn’t required.
Previous Post

Next article