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 step-by-step approach:

Initialize a Probability Array: Create an array dp of length n+1 to store the probability of reaching each score from 0 to n. Initialize dp[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 previous maxPts 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 to n to obtain the final result.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k + maxPts - 1:
            return 1.0

        dp = [0.0] * (n + 1)
        dp[0] = 1.0
        wsum = 1.0  # Window sum to store the sum of previous maxPts probabilities

        for i in range(1, n + 1):
            dp[i] = wsum / maxPts
            if i < k:
                wsum += dp[i]
            if i - maxPts >= 0:
                wsum -= dp[i - maxPts]

        return sum(dp[k:])

Explanation:

wsum stores the sum of the previous maxPts 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 bottom-up 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 sub-problems 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def new21Game(self, N, K, maxPts):
        if K == 0:
            return 1.0
        if N >= K - 1 + maxPts:
            return 1.0

        dp = [0.0] * (N + 1)

        probability = 0.0  # dp of N or less points.
        windowSum = 1.0  # Sliding required window sum
        dp[0] = 1.0
        for i in range(1, N + 1):
            dp[i] = windowSum / maxPts

            if i < K:
                windowSum += dp[i]
            else:
                probability += dp[i]

            if i >= maxPts:
                windowSum -= dp[i - maxPts]

        return probability

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 10-5 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 method new21Game.
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 and windowSum are initialized, and a list dp 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