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 = 10 Output: 0.73278
Constraints:
0 <= k <= n <= 1041 <= maxPts <= 104
Solutions
Solution 1: Memoized Search
We design a function dfs(i), which represents the probability that when the current score is i, the final score does not exceed n when we stop drawing numbers. The answer is dfs(0).
The calculation method of function dfs(i) is as follows:
- If i \ge k, then we stop drawing numbers. If i \le n, return 1, otherwise return 0;
- Otherwise, we can draw the next number j in the range [1,..maxPts], then dfs(i) = 1⁄maxPts ∑_{j=1}^{maxPts} dfs(i+j).
Here we can use memoized search to accelerate the calculation.
The time complexity of the above method is O(k × maxPts), which will exceed the time limit, so we need to optimize it.
When i \lt k, the following equation holds:
$$ \begin{aligned} dfs(i) &= (dfs(i + 1) + dfs(i + 2) + \cdots + dfs(i + \textit{maxPts})) / \textit{maxPts} & (1) \end{aligned} $$
When i \lt k - 1, the following equation holds:
$$ \begin{aligned} dfs(i+1) &= (dfs(i + 2) + dfs(i + 3) + \cdots + dfs(i + \textit{maxPts} + 1)) / \textit{maxPts} & (2) \end{aligned} $$
Therefore, when i \lt k-1, we subtract equation (2) from equation (1) to get:
$$ \begin{aligned} dfs(i) - dfs(i+1) &= (dfs(i + 1) - dfs(i + \textit{maxPts} + 1)) / \textit{maxPts} \end{aligned} $$
That is:
$$ \begin{aligned} dfs(i) &= dfs(i + 1) + (dfs(i + 1) - dfs(i + \textit{maxPts} + 1)) / \textit{maxPts} \end{aligned} $$
If i=k-1, we have:
$$ \begin{aligned} dfs(i) &= dfs(k - 1) = (dfs(k) + dfs(k + 1) + \cdots + dfs(k + \textit{maxPts} - 1)) / \textit{maxPts} & (3) \end{aligned} $$
We assume there are i numbers not exceeding n, then k+i-1 ≤ n, and since i≤ maxPts, we have i ≤ min(n-k+1, maxPts), so equation (3) can be written as:
$$ \begin{aligned} dfs(k-1) &= \min(n-k+1, \textit{maxPts}) / \textit{maxPts} \end{aligned} $$
In summary, we have the following state transition equation:
$$ \begin{aligned} dfs(i) &= \begin{cases} 1, & i \geq k, i \leq n \ 0, & i \geq k, i \gt n \ \min(n-k+1, \textit{maxPts}) / \textit{maxPts}, & i = k - 1 \ dfs(i + 1) + (dfs(i + 1) - dfs(i + \textit{maxPts} + 1)) / \textit{maxPts}, & i < k - 1 \end{cases} \end{aligned} $$
Time complexity O(k + maxPts), space complexity O(k + maxPts). Where k is the maximum score.
class Solution: def new21Game(self, n: int, k: int, maxPts: int) -> float: @cache def dfs(i: int) -> float: if i >= k: return int(i <= n) if i == k - 1: return min(n - k + 1, maxPts) / maxPts return dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts return dfs(0)(code-box)
Solution 2: Dynamic Programming
We can convert the memoized search in Solution 1 into dynamic programming.
Define f[i] to represent the probability that when the current score is i, the final score does not exceed n when we stop drawing numbers. The answer is f[0].
When k ≤ i ≤ min(n, k + maxPts - 1), we have f[i] = 1.
When i = k - 1, we have f[i] = min(n-k+1, maxPts) / maxPts.
When i \lt k - 1, we have f[i] = f[i + 1] + (f[i + 1] - f[i + maxPts + 1]) / maxPts.
Time complexity O(k + maxPts), space complexity O(k + maxPts). Where k is the maximum score.
class Solution: def new21Game(self, n: int, k: int, maxPts: int) -> float: f = [0] * (k + maxPts) for i in range(k, min(n + 1, k + maxPts)): f[i] = 1 f[k - 1] = min(n - k + 1, maxPts) / maxPts for i in range(k - 2, -1, -1): f[i] = f[i + 1] + (f[i + 1] - f[i + maxPts + 1]) / maxPts return f[0](code-box)
