Approach #1: Dynamic Programming [Accepted]
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
f(x) be the answer when we already have
x points. When she has between
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 time, by maintaining the numerator .
As we calculate each
dp[k] = S / W, we maintain the correct value of this numerator .
- 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.