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 previousW
points, divided byW
. - To calculate this sum, we maintain a window sum of the probability of the last
W
points. - If
i
is less thanK
, we would take this point and so adddp[i]
to our window sum. - If
i
is more thanK
, the game ends and and we adddp[i]
to our answer. - If
i
is more thanW
, then we have moved on from the situation and it is no longer in our window of the lastW
points, and we subtractdp[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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.