Leetcode 837. New 21 Game

Problem Explanation

The problem is about a card game that Alice is playing which is slightly similar to the game "21". Alice keeps drawing cards until her total score is less than K. Each card she draws is an integer within the range [1, W] and each draw has equal probabilities. The problem is asking for the probability that she has N or less points.

For example, let's take N=6, K=1 and W=10. Alice can draw a card from 1 to 10. And she need to stop when the score is 1 or more. Here, the total possible cards she could get are 10. But we are asking probability that she has 6 or less points. In this scenario, the possible cards could be 1,2,3,4,5,6. So, totally 6 possible cards are there for our required probability which will eventually give the probability of 0.6.

Solution Approach

We can approach this problem using dynamic programming. Intuitively, we can create a probability distribution dp where dp[x] is the probability that Alice has x points.

Let's break down how we would update our dp array:

• The probability to get i points is the rolling window sum of the probabilities to get the previous W points, divided by W.
• To calculate this sum, we maintain a window sum of the probability of the last W points.
• If i is less than K, we would take this point and so add dp[i] to our window sum.
• If i is more than K, the game ends and and we add dp[i] to our answer.
• If i is more than W, then we have moved on from the situation and it is no longer in our window of the last W points, and we subtract dp[i - W] from our window sum.

We then return our answer as the output.

Example

For example take N=21, K=17 and W=10. Initially we might have our dp array as [1.0,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,0,10,0,0,..10000].

Let's take an example for i=3 which is less than k:

• Here the window contains dp[0],dp[1],dp[2]
• so our dp[3] becomes (dp[0]+dp[1]+dp[2])/W=(1.0+0+0.2)/10=0.12
• then add dp[3] to our window sum.

now lets see for i=18 which is more than k:

• Here the window contains dp[8],dp[9],dp[10],dp[11],dp[12],dp[13],dp[14],dp[15],dp[16],dp[17].
• so our dp[18] becomes (sum of window elements)/10
• But the game ends at this stage so we add dp[18] to our answer.

Based on the steps shown above, following are the implementations in C++, Java, Python and Javascript.

C++ Solution

1
2c++
3class Solution {
4 public:
5  double new21Game(int n, int k, int maxPts) {
6    if (k == 0 || n >= k - 1 + maxPts)
7      return 1.0;
8
9    double ans = 0.0;
10    vector<double> dp(n + 1);  // dp[i] is the prob to have i points
11    dp[0] = 1.0;
12    double windowSum = dp[0];  // sum of window elements from last W points
13
14    for (int i = 1; i <= n; ++i) {
15      dp[i] = windowSum / maxPts; // calculate dp[i]
16      if (i < k)
17        windowSum += dp[i];  // if game continues add dp[i] into window sum
18      else 
19        ans += dp[i];  // if game ends add dp[i] into the answer sum
20      if (i - maxPts >= 0)
21        windowSum -= dp[i - maxPts]; //remove the exiting point when exceeds window
22    }
23
24    return ans; // returning final ans as our ouptput
25  }
26};

Python Solution

1
2python
3class Solution:
4    def new21Game(self, n: int, k: int, maxPts: int) -> float:  
5        if k == 0 or n >= k - 1 + maxPts:
6            return 1.0
7
8        dp = [0.0] * (n + 1)  # dp[i] is the prob to have i points
9        dp[0] = 1.0
10        windowSum = dp[0]  # sum of window elements from last W points
11
12        for i in range(1, n + 1):
13            dp[i] = windowSum / maxPts  # calculate dp[i]
14            if i < k:
15                windowSum += dp[i]  # if game continnues add dp[i] into window sum
16            else:
17                ans += dp[i]  # if game ends add dp[i] into the answer sum
18            if i - maxPts >= 0:
19                windowSum -= dp[i - maxPts]  #remove the exiting point when exceeds window
20
21        return sum(dp[k:])  # returning final ans as our ouptput

Java Solution

1
2java
3class Solution {
4    public double new21Game(int n, int k, int maxPts) {
5        if (k == 0 || n >= k - 1 + maxPts) {
6            return 1.0;
7        }
8            
9        double[] dp = new double[n + 1];  // dp[i] is the prob to have i points
10        dp[0] = 1.0;
11        double windowSum = dp[0];  // sum of window elements from last 10 points
12
13        for (int i = 1; i <= n; ++i) {
14            dp[i] = windowSum / maxPts;  // calculate dp[i]
15            if (i < k){
16                windowSum += dp[i];  // if game continnues add dp[i] into window sum
17            }
18            else{
19                ans += dp[i];  // if game ends add dp[i] into the answer sum
20            }
21            if (i - maxPts >= 0){
22                windowSum -= dp[i - maxPts];  //remove the exiting point when exceeds window
23            }
24        }
25
26        double ans = 0.0;
27        for (int i = k; i <= n; i++) {
28            ans += dp[i];  // calculate final ans
29        }
30        return ans;
31    }
32}

JavaScript Solution

1
2javascript
3var new21Game = function(n, k, maxPts) {
4    if (k == 0 || n >= k + maxPts) {
5        return 1.0;
6    }
7        
8    let dp = Array(n + 1).fill(0);  // dp[i] is the prob to have i points
9    dp[0] = 1.0;
10    let windowSum = 1.0;    // sum of window elements from last W points
11    let ans = 0.0;
12    
13    for (let i = 1; i <= n; i++) {
14        dp[i] = windowSum / maxPts;  // calculate dp[i]
15        if (i < k)
16            windowSum += dp[i];  // if game continues, add dp[i] into window sum
17        else 
18            ans += dp[i];  // if game ends, add dp[i] into the answer sum
19        if (i - maxPts >= 0)
20            windowSum -= dp[i - maxPts];  //remove the exiting point when exceeds window
21    }
22    
23    return ans;  //returning final ans as our output
24    
25};

In conclusion, the presented problem statement is a typical probability-based problem from dynamic programming. Despite the intricate complexity of the problem, a strong understanding of how the game functions, card probabilities and dynamic programming makes the problem a lot easier to solve. In the presented solution, we keep a track of the rolling window sum of the probabilities of the last W points to logically calculate the future points probabilities and add to our solution if the game ends. Ultimately, we calculate the final answer with all accumulated points probabilities which is then returned as our answer.

This step-by-step guide provides a clear solution and approach to solve the problem in Python, JavaScript, Java and C++, making it convenient to implement in a language of your choice. The key to solving such dynamic programming problems is understanding the underlying patterns and keeping track of relevant data as you compute the solution.