AlgorithmsComputer Science TopicsDynamic ProgrammingLeetCode SolutionsMedium DifficultyProgramming InterviewsPython

LeetCode 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.

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

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;
}
}
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

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