#### Approach #1: Dynamic Programming [Accepted]

**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 time, by maintaining the numerator .

As we calculate each `dp[k] = S / W`

, we maintain the correct value of this numerator .

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

Analysis written by: @awice.