837. New 21 Game
Problem Description
In this problem, Alice plays a game similar to "21," where her objective is to accumulate points through random draws without exceeding a certain threshold. Alice starts with 0 points and continues to draw integers from 1 up to maxPts until the total points reach or exceed k. The goal of the problem is to calculate the probability that Alice finishes the game with n or fewer points. The points gained from each draw are independent and have equal probability. One key condition is that if Alice's score is already k or more, she stops drawing cards. The result should be accurate within a tolerance level of 10^-5.
Intuition
The solution involves using dynamic programming, specifically in a recursive manner with memoization to cache previously computed results, as seen by the @cache decorator. The process can be thought of as a depth-first search (DFS), where we explore each possible sum Alice could attain starting from 0 and moving forward.
The algorithm starts with a function dfs that takes the current score i as an argument and returns the probability of Alice having n or fewer points when starting with i points. If i is greater than or equal to k, Alice can no longer draw cards, and we return 1 if i is less than or equal to n (successful outcome), and 0 otherwise (failure).
The base cases cover when i is k or more (stop drawing), and a special optimization when i is exactly k - 1. In this case, Alice has only one draw left, so we calculate the probability based on how many points from 1 to maxPts would be successful.
The recursive step of the algorithm tries to calculate the probabilities for the next draw based on previous calculations, thus reducing the number of calculations needed and using the principle of mathematical expectation. It combines the probabilities of all possible outcomes from the next draw and subtracts the probabilities beyond the maximal points Alice needs to win, as she stops drawing after reaching k.
By calling dfs(0), we're initiating our search from a score of 0 and climbing up to find out what the probability would be for Alice to end up with n or fewer points, which provides us with the final answer.
Learn more about Math, Dynamic Programming and Sliding Window patterns.
Which technique can we use to find the middle of a linked list?
Solution Approach
The solution provided here is a recursive implementation that makes use of dynamic programming principles and incorporates memoization to store the results of previously computed probabilities. This is to prevent recomputing the probability for each score, which would otherwise lead to a very inefficient algorithm with a lot of repeated work.
The data structure used for memoization is the internal cache provided by Python's functools library, which is applied using the @cache decorator on top of the recursive function dfs.
Now, breaking down the solution:
dfs(i: int) -> float: This is the main function that computes the probability of Alice ending the game withipoints by drawing numbers.- If
iis greater than or equal tok, Alice must stop drawing cards. Therefore, the probability of Alice havingnor fewer points is 1 ifiis less than or equal ton, and zero otherwise because she can't have more thannpoints under the given conditions. - The case of
i == k - 1is a special base case, which accounts for the last draw before reaching the stopping point atk. In this situation, it's possible to precisely calculate the probability because there's only one possible draw. It is the ratio of the count of numbers leading to a total score ofnor fewer points to themaxPts. - For other cases, the solution uses the recursive formula
dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts. Here's what it does:dfs(i + 1)gives the probability starting at the next point.- Then we include the probabilities for each point between
i + 1andi + maxPts, ensuring that we account for the varying outcomes of the next draw. This is accomplished by adding(dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts, which normalizes the sum of probabilities over the range of possible next draws, by subtracting the sum from the point that ismaxPts + 1steps away from the current point and dividing bymaxPtswhich is the range of outcomes for a single draw.
The function dfs(0) is called to start the process from a score of 0 and computes the desired probability using this algorithm. It leverages the cache to store intermediate calculations, making the solution efficient enough to handle larger inputs.
In summary, this solution approach utilizes a combination of recursion, memoization, and mathematical probability calculations to efficiently solve the problem of calculating the chance of Alice's success in this card-game-based simulation.
Which two pointer techniques do you use to check if a string is a palindrome?
Example Walkthrough
Let's assume maxPts = 10, k = 21, and n = 20 for our simplified example to illustrate the solution approach.
Step 1: Initial Call
We start by calling dfs(0) which signifies that Alice is starting the game with 0 points, and we wish to find out the probability that she ends up with 20 points or fewer by the time she decides to stop drawing cards.
Step 2: Recursive Calls and Memoization
When dfs(i) is called, we first check if i is greater than or equal to k (which is 21 in our example). If i is 21 or more, we return 1 if i is less than or equal to n, which is not the case here so recursion won't start at 21 or more.
Step 3: Handle Special Case
When i is exactly 20 (which is k - 1), the function checks the special case. At i = 20, Alice can only make one draw. She succeeds if she draws 1 point, which is the only possibility within the given maxPts without exceeding n. Thus, the probability in this case would be 1 / maxPts, which is 1 / 10.
Step 4: Recursion for General Case
For any i less than 20, we calculate the probability recursively. Take dfs(19) for example:
- We first look at
dfs(20)(which is already established as1/10). - Then, we consider the recursion step,
(dfs(19 + 1) - dfs(19 + maxPts + 1)) / maxPts. We need to calculatedfs(19 + maxPts + 1)which isdfs(30)here, but since30 >= k, its value is0. - Thus, for
dfs(19), the probability becomesdfs(20) + (dfs(20) - dfs(30)) / maxPts. Substituting the known values, we get1/10 + (1/10 - 0) / 10which is1/10 + 1/100equal to0.11(or11/100).
Step 5: Continue until Base Case or Cache Hit
The algorithm continues like this for dfs(18), dfs(17), ... until it either reaches a base case or hits a cached value. At each step, it uses the probabilities from the higher points to calculate the current point's probability while ensuring it doesn't calculate the same value multiple times thanks to memoization.
Step 6: Final Result
This continues until we reach back to the initial call, dfs(0), at which point all required probabilities have been cached and are used to find the probability that Alice ends the game with 20 or fewer points starting from 0. This compound probability considering all the paths of play Alice could take is the final result returned to the caller.
Solution Implementation
1from functools import lru_cache
2
3class Solution:
4 def new21Game(self, N: int, K: int, maxPoints: int) -> float:
5 # Use an LRU cache to cache results and avoid re-computation.
6 @lru_cache(None)
7 def dfs(current_points: int) -> float:
8 # Base condition: If current points are at or beyond K,
9 # the game stops; return 1.0 if not beyond N, otherwise 0.0.
10 if current_points >= K:
11 return float(current_points <= N)
12
13 # If we are at the last point before K, the probability of
14 # getting a final score not more than N depends on how many
15 # points would lead to a score within the [K, N] range,
16 # divided by the maximum number of points we can get at this draw.
17 if current_points == K - 1:
18 return min(N - K + 1, maxPoints) / maxPoints
19
20 # Recursively calculate the probability of winning by either
21 # drawing a card of points 1 up to maxPoints from the current score. The probability
22 # is a difference of probabilities of getting the next score, and the score that is
23 # 'maxPoints' away from current + 1, because that's no longer reachable in one draw.
24 # The total is divided by maxPoints to get the average probability.
25 return dfs(current_points + 1) + (dfs(current_points + 1) - dfs(current_points + maxPoints + 1)) / maxPoints
26
27 # Start DFS from 0 points to calculate the probability of winning.
28 return dfs(0)
291class Solution {
2 private double[] probabilityLookup; // Cached probabilities for intermediate results.
3 private int maxFinalPoints, pointsToStop, maxPointsPerDraw;
4
5 // The new21Game method where the game's calculation starts.
6 public double new21Game(int maxFinalPoints, int pointsToStop, int maxPointsPerDraw) {
7 this.maxFinalPoints = maxFinalPoints;
8 this.pointsToStop = pointsToStop;
9 this.maxPointsPerDraw = maxPointsPerDraw;
10 this.probabilityLookup = new double[pointsToStop]; // Cache array initialized for stopping points.
11 return calculateProbability(0); // Start calculating from point 0.
12 }
13
14 // Recursive method to calculate the probability of winning.
15 private double calculateProbability(int currentPoints) {
16 // If we've reached the stopping point, return 1 if it's a win, 0 if it's a loss.
17 if (currentPoints >= pointsToStop) {
18 return currentPoints <= maxFinalPoints ? 1 : 0;
19 }
20
21 // Base case for the stopping point.
22 if (currentPoints == pointsToStop - 1) {
23 return Math.min(maxFinalPoints - pointsToStop + 1, maxPointsPerDraw) / (double) maxPointsPerDraw;
24 }
25
26 // If we've already calculated the probability for these points, return it.
27 if (probabilityLookup[currentPoints] != 0) {
28 return probabilityLookup[currentPoints];
29 }
30
31 // Recursive call and formula to calculate the probability.
32 // We advance one point and subtract the probability of going out of bounds, normalized by the max points per draw.
33 probabilityLookup[currentPoints] = calculateProbability(currentPoints + 1)
34 + (calculateProbability(currentPoints + 1) - calculateProbability(currentPoints + maxPointsPerDraw + 1))
35 / maxPointsPerDraw;
36
37 return probabilityLookup[currentPoints];
38 }
39}
401#include <vector>
2#include <functional>
3
4class Solution {
5public:
6 // Calculates the probability of winning the 21 game.
7 double new21Game(int n, int k, int maxPts) {
8 std::vector<double> dp(k + maxPts, 0.0); // Dynamic programming vector initialized with zeros.
9 double wSum = 0.0; // Window sum to hold the sum of probabilities of the last 'maxPts' states.
10 double result;
11
12 // Initialize the base cases
13 for (int i = k; i < k + maxPts && i <= n; ++i) {
14 dp[i] = 1.0;
15 wSum += 1.0; // Only scores <= n can lead to a win.
16 }
17
18 // The last score leading to a win is from 'k-1', if there are more window states than needed, only count as much as 'n-k+1'.
19 if (k > 0) {
20 dp[k - 1] = wSum / maxPts;
21 }
22
23 // Iterate backwards to fill in the dp vector.
24 for (int i = k - 2; i >= 0; --i) {
25 // Sliding window for the sum of probabilities.
26 dp[i] = wSum / maxPts;
27 wSum += dp[i]; // When sliding the window, add the current dp value to the window sum.
28 wSum -= dp[i + maxPts]; // Remove the dp value going out of the window.
29 }
30
31 // The result is the probability of being in state 0 with the game continuing.
32 result = dp[0];
33
34 return result;
35 }
36};
371// Holds memoized results for optimization
2const memo: number[] = new Array(k).fill(0);
3
4// Define a recursive function to calculate the probability
5// i: current sum of points
6function dfs(i: number): number {
7 // Base case: When i is at least k but not greater than n, it means the game ends successfully
8 if (i >= k) {
9 return i <= n ? 1 : 0;
10 }
11 // Edge case: When we're at the last draw that might push the score over k
12 if (i === k - 1) {
13 // The probability will be the fraction of possible points that won't exceed n
14 return Math.min(n - k + 1, maxPts) / maxPts;
15 }
16 // If the value is already computed, return it to avoid re-calculation
17 if (memo[i] !== 0) {
18 return memo[i];
19 }
20 // Recursive relation:
21 // The probability of reaching current 'i' is the probability of 'i+1'
22 // plus the correction term which accounts for the sliding window effect of the next 'maxPts' states
23 // This term is divided by 'maxPts' which represents the uniform probability of drawing each point from 1 to maxPts.
24 memo[i] = dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts;
25 return memo[i];
26}
27
28// Begin the game from zero points
29return dfs(0);
30Which technique can we use to find the middle of a linked list?
Time and Space Complexity
The given code snippet is an implementation of a dynamic programming solution to solve the 21 Game problem. The time and space complexity analysis is as follows:
Time Complexity:
The time complexity of the dfs function is based on two factorsโthe range of possible scores [0, k) and the number of recursive calls made for each score. Let's analyze it step by step:
- We can have at most
kdifferent states since the recursion stops oncei >= k. - For each state
i, thedfsfunction is memoizedโmeaning results of previous calls are cached to avoid re-computation. - For each state
i, thedfsfunction makes a recursive call todfs(i + 1)and accesses the cached results ofdfs(i + 1)anddfs(i + maxPts + 1)to calculate the current state's probability. - Since we're caching the results, each state is computed only once, and the recursion has a depth of at most
maxPts.
Combining these observations, the time complexity can be calculated as O(k * maxPts), where 'k' is the number of states up to when the game stops and maxPts is the number of recursive branches we explore before hitting memoized states.
Space Complexity:
The space complexity is determined mostly by the space needed for caching the results of the dfs function and the call stack during the recursion:
- We're using memoization, and therefore need cache space for each potential state from
[0, k)which gives usO(k). - The call stack's maximum depth would be
maxPtsin the worst-case scenario, due to the nature of thedfsfunction making recursive calls onlymaxPtstimes before reaching a memoized value or a base case.
So, the space complexity is O(k + maxPts), which simplifies to O(k) if k is larger than maxPts, as the cache storage is the dominant term.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
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.