New 21 Game
This problem can be solved using dynamic programming. The idea is to calculate the probabilities of reaching each possible score from 0 to n
, taking into account the constraint that Alice stops drawing numbers when she gets k
or more points.
Here’s a stepbystep approach:
 Initialize a Probability Array: Create an array
dp
of lengthn+1
to store the probability of reaching each score from 0 ton
. Initializedp[0] = 1
since the probability of starting with 0 points is 1.  Iterate Through Scores: Iterate through the scores from 1 to
n
, and calculate the probability of reaching each score.  Calculate Probability for Each Score: For each score
i
, calculate the probability by considering the previousmaxPts
scores, and distribute the probability evenly among them.  Handle the Stopping Condition: If the current score is greater or equal to
k
, Alice stops drawing, so we need to take this into account when calculating probabilities.  Calculate the Result: Sum the probabilities for scores from
k
ton
to obtain the final result.
Here’s the code:


Explanation:
wsum
stores the sum of the previousmaxPts
probabilities, which is used to calculate the probability for the current score. We add the current probability to the window sum if the current score is less than
k
.  We remove the probability that is now outside the window of the previous
maxPts
scores.
This code runs in ( O(n) ) time complexity, where ( n ) is the given input, and uses ( O(n) ) additional space to store the probabilities.
10 Prerequisite LeetCode Problems
“New 21 Game” involves dynamic programming and probability calculation. Here are 10 problems to prepare:
Climbing Stairs (LeetCode 70): This problem involves the same kind of dynamic programming approach required for the “New 21 Game”.
Best Time to Buy and Sell Stock (LeetCode 121): It is another dynamic programming problem that helps in understanding when to make certain decisions that may affect the outcome.
Coin Change (LeetCode 322): This problem is about finding the fewest number of coins that you need to make up a given amount, which involves a similar dynamic programming approach.
Unique Paths (LeetCode 62): Another dynamic programming problem. It is about finding all unique paths in a grid which could be related to finding different ways of reaching to a certain points in a game.
House Robber (LeetCode 198): This problem is about making decisions at each step for an optimal solution which is a common scenario in dynamic programming problems.
Fibonacci Number (LeetCode 509): Understanding how to solve this problem can aid in grasping the bottomup dynamic programming approach.
Minimum Path Sum (LeetCode 64): This problem involves finding a path in a grid which minimizes the total sum which helps to understand dynamic programming.
Maximum Subarray (LeetCode 53): This problem can help you to understand how to handle subproblems in dynamic programming.
Partition Equal Subset Sum (LeetCode 416): This problem involves a similar dynamic programming approach where you have to decide whether to include or exclude a number at each step.
Pascal’s Triangle (LeetCode 118): Understanding the concept of dynamic programming is the key to solve this problem.


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, maxPts], where maxPts is an integer. Each draw is independent and the outcomes have equal probabilities.
Alice stops drawing numbers when she gets k or more points.
Return the probability that Alice has n or fewer points.
Answers within 105 of the actual answer are considered accepted.
Example 1:
Input: n = 10, k = 1, maxPts = 10 Output: 1.00000 Explanation: Alice gets a single card, then stops.
Example 2:
Input: n = 6, k = 1, maxPts = 10 Output: 0.60000 Explanation: Alice gets a single card, then stops. In 6 out of 10 possibilities, she is at or below 6 points. Example 3:
Input: n = 21, k = 17, maxPts = 10 Output: 0.73278
Constraints:
0 <= k <= n <= 10^4 1 <= maxPts <= 10^4
Language Agnostic Coding Drills
Class and Method Definition: Like many programming languages, Python uses classes to define objects. In this case, a class
Solution
is defined with a methodnew21Game
.Basic Conditional Statements: The
if
statements are used to handle the simple cases first where the probabilities are certain (1.0). This is a common strategy to simplify the remainder of the problem.Initialization of Variables and Lists: The variables
probability
andwindowSum
are initialized, and a listdp
is created.dp
seems to be a dynamic programming table.For Loop and List Indexing: A for loop is used to iterate over the possible values. In each iteration, the DP table
dp
is updated based on its previous values.Floating Point Division: The
windowSum / maxPts
operation is a floating point division, which returns a float in Python.Conditional Increment/Decrement of Variables: The
windowSum
variable is conditionally incremented or decremented based on certain conditions. This is typical in sliding window problems where the sum of a certain window of values is maintained.Return Statement: The function returns the final probability.
Arranging the drills in increasing order of difficulty:
 Class and Method Definition
 Basic Conditional Statements
 Initialization of Variables and Lists
 Floating Point Division
 For Loop and List Indexing
 Conditional Increment/Decrement of Variables
 Return Statement
Targeted Drills in Python
Class and Method Definition
1 2 3 4 5 6
class MyClass: def my_method(self, a, b): return a + b obj = MyClass() print(obj.my_method(2, 3)) # Output should be 5
Basic Conditional Statements
1 2 3 4 5 6 7 8 9
def compare_values(a, b): if a > b: return "a is greater than b" elif a < b: return "a is less than b" else: return "a is equal to b" print(compare_values(5, 3)) # Output should be "a is greater than b"
Initialization of Variables and Lists
1 2 3 4
my_variable = 10 my_list = [0] * 10 print(my_variable) # Output should be 10 print(my_list) # Output should be [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Floating Point Division
1 2 3
a = 10 b = 3 print(a / b) # Output should be 3.3333333333333335
For Loop and List Indexing
1 2 3 4
my_list = [1, 2, 3, 4, 5] for i in range(len(my_list)): my_list[i] = my_list[i] ** 2 print(my_list) # Output should be [1, 4, 9, 16, 25]
Conditional Increment/Decrement of Variables
1 2 3 4 5 6 7 8 9
def modify_value(a, b): if a > b: a = 1 else: a += 1 return a print(modify_value(5, 3)) # Output should be 4 print(modify_value(2, 3)) # Output should be 3
Return Statement
1 2 3 4
def square(a): return a ** 2 print(square(5)) # Output should be 25