New 21 Game
Problem Description
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 = 10Output: 0.73278
Constraints:
0 <= k <= n <= 1041 <= maxPts <= 104
Solve it on LeetCode
Approaches
1. Brute Force Approach
In this initial approach, we simulate every possible game outcome up to the maximum point. The idea is to use recursion to try every possible draw of cards and compute the probability of reaching the target score.
Intuition:
- We simulate each turn by drawing a card from 1 to
K. - Recursively calculate the probabilities of reaching a score greater than or equal to
N. - This recursion depth can get very large and become inefficient for larger values of
NandK.
Code:
- Time Complexity: O((K + maxPts)^maxPts)
- Space Complexity: O(K + maxPts)
2. Dynamic Programming Approach
To improve efficiency, we switch to a Dynamic Programming technique, utilizing a DP array to store probabilities.
Intuition:
- Define
dp[x]as the probability of getting exactlyxpoints. - Iteratively calculate probabilities for each score from 0 up to
K. - For scores greater than
K, if the score is within the range[K, N], then it contributes to the total probability outcome.
Code:
- Time Complexity: O(N)
- Space Complexity: O(N)
3. Optimized DP Approach
The optimized DP approach reduces space usage by using a sliding window over the DP array, effectively reducing it from O(N) to O(maxPts).
Intuition:
- Instead of maintaining a whole DP array, keep a rolling sum of probabilities that will be averaged out.
- This rolling window approach ensures that we only maintain necessary elements from the DP array within the range
[i-maxPts, i].
Code:
- Time Complexity: O(K + maxPts)
- Space Complexity: O(maxPts)