LeetCode [837] New 21 Game

 837. New 21 Game

Medium

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.

Explanation from KaiPeng21 @LeetCode

When the game ends, the point is between K and K-1+W
    What is the probability that the the point is less than N?
    - If N is greater than K-1+W, probability is 1
    - If N is less than K, probability is 0
    
    If W == 3 and we want to find the probability to get a 5
    - You can get a card with value 1, 2, or 3 with equal probability (1/3)
    - If you had a 4 and you get a 1: prob(4) * (1/3)
    - If you had a 3 and you get a 2: prob(3) * (1/3)
    - If you had a 2 and you get a 3: prob(2) * (1/3)
    - If you had a 1, you can never reach a 5 in the next draw
    - prob(5) = prob(4) / 3 + prob(3) / 3 + prob(2) /3
    
    To generalize:
    The probability to get point K is
    p(K) = p(K-1) / W + p(K-2) / W + p(K-3) / W + ... p(K-W) / W
    
    let wsum = p(K-1) + p(K-2) + ... + p(K-W)
    p(K) = wsum / W
    
    dp is storing p(i) for i in [0 ... N]
    - We need to maintain the window by
      adding the new p(i), 
      and getting rid of the old p(i-w)
    - check i >= W because we would not have negative points before drawing a card
      For example, we can never get a point of 5 if we drew a card with a value of 6
    - check i < K because we cannot continue the game after reaching K
      For example, if K = 21 and W = 10, the eventual point is between 21 and 30
      To get a point of 27, we can have:
      - a 20 point with a 7
      - a 19 point with a 8
      - a 18 point with a 9
      - a 17 point with a 10
      - but cannot have 21 with a 6 or 22 with a 5 because the game already ends

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution { public double new21Game(int N, int K, int W) { //the possible result range is [K, K-1+W] if(N>K-1+W) return 1.0; if(N<K) return 0; if(K==0) return 1.0;//not drawing any card. 0<=N double[] dp = new double[N+1]; dp[0] = 1; double Wsum = 1.0;//sum the probablities in a W-size window double ret = 0; for(int i=1; i<K; ++i){ dp[i] = Wsum/W; Wsum += dp[i]; if(i-W>=0){//window size is W+1 Wsum -= dp[i-W]; } } for(int i=K; i<=N; i++){ dp[i] = Wsum/W; //stop drawing after reaching K //Wsum += dp[i]; if(i-W>=0){//window size is W+1 Wsum -= dp[i-W]; } ret += dp[i]; } return ret; } }