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 = 10Output:1.00000Explanation:Alice gets a single card, then stops.

**Example 2:**

Input:N = 6, K = 1, W = 10Output:0.60000Explanation: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 = 10Output:0.73278

**Note:**

`0 <= K <= N <= 10000`

`1 <= W <= 10000`

- Answers will be accepted as correct if they are within
`10^-5`

of the correct answer. - 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.