New 21 Game
Alice plays the following game, risking her mental health:
Alice starts with 0 points and draws numbers while she has fewer than k points. During each draw, she gains an integer number of points randomly from 1 to maxPts, where each value is equally likely.
Return the probability that Alice has n or fewer points when she stops drawing.
Examples
Input: [10,1,10]
Output: 1
Input: [6,1,10]
Output: 0.6
Hints
Use dynamic programming to compute the probability of reaching each point value `x` (where `x` ranges from `0` to `n`). Initialize `dp[0] = 1` since Alice starts with `0` points. For each `x` from `1` to `n`, compute `dp[x]` as the average of `dp[x - i]` for all `i` in `1` to `maxPts` where `x - i >= 0`.
Optimize the DP approach by recognizing that the probability of reaching `x` depends only on the previous `maxPts` states. Use a sliding window or prefix sums to reduce the time complexity from O(n * maxPts) to O(n).
Further optimize by using matrix exponentiation or generating functions to compute the probabilities in O(log n) time, especially useful when `n` is very large (e.g., up to 1e9). This involves representing the recurrence relation as a matrix and raising it to the power of `k` to find the probability distribution after `k` steps.
Related Problems
New 21 Game
Alice plays the following game, risking her mental health: