837. New 21 Game.md

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:

• 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

• mine

  • Java

    got from the leetcode's solution Runtime: 3 ms, faster than 95.04%, Memory Usage: 39.4 MB, less than 14.29% of Java online submissions

    //O(N)time O(N+W)space
    public double new21Game(int N, int K, int W) {
        if(K == 0){
            return 1.0;
        }
        double[] dp = new double[N + W];
        for(int i = K; i <= N; i++){
            dp[i] = 1.0;
        }
        dp[K - 1] = 1.0 / W * Math.min(N - K + 1, W);
        for(int i = K - 2; i >= 0; i--){
            dp[i] = dp[i + 1] - (dp[i + W + 1] - dp[i + 1]) / W;
        }
        return dp[0];
    }
    

---

• the moss votes

  Runtime: 3 ms, faster than 95.04%, Memory Usage: 38.8 MB, less than 14.29% of Java online submissions

  //O(N)time O(N)space
  public double new21Game(int N, int K, int W) {
      if (K == 0 || N >= K + W) return 1;
      double dp[] = new double[N + 1],  Wsum = 1, res = 0;
      dp[0] = 1;
      for (int i = 1; i <= N; ++i) {
          dp[i] = Wsum / W;
          if (i < K) Wsum += dp[i]; else res += dp[i];
          if (i - W >= 0) Wsum -= dp[i - W];
      }
      return res;
  }
  

---

• the leetcode's solution

  Runtime: 3 ms, faster than 95.04%, Memory Usage: 38.6 MB, less than 14.29% of Java online submissions

  //O(N + W)time  O(N + W)space
  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];
  }