New 21 Game - Solution & Explanation

The idea is to use an array to keep track of the probability of reaching exactly a particular score. We will use a sliding window approach to maintain the sum of probabilities for the most recent maxPts scores dynamically. This allows us to efficiently update probabilities as we simulate Alice drawing numbers up to n.

In this Python implementation, we initialize a probability array dp where dp[i] represents the probability of having exactly i points. The window sum is managed carefully so that only relevant probabilities affect the current probability determination. By sliding the window sum, we efficiently update the probabilities.

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) = \frac{1}{maxPts} sum_{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 times 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 + maxPts)) / 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 + maxPts + 1)) / 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 + maxPts + 1)) / maxPts \end{aligned}

\begin{aligned} dfs(i) &= dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts \end{aligned}

If i=k-1, we have:

\begin{aligned} dfs(i) &= dfs(k - 1) = (dfs(k) + dfs(k + 1) + cdots + dfs(k + maxPts - 1)) / maxPts & (3) \end{aligned}

We assume there are i numbers not exceeding n, then k+i-1 leq n, and since ileq maxPts, we have i leq min(n-k+1, maxPts), so equation (3) can be written as:

\begin{aligned} dfs(k-1) &= min(n-k+1, maxPts) / maxPts \end{aligned}

\begin{aligned} dfs(i) &= \begin{cases} 1, & i geq k, i leq n \ 0, & i geq k, i \gt n \ min(n-k+1, maxPts) / maxPts, & i = k - 1 \ dfs(i + 1) + (dfs(i + 1) - dfs(i + maxPts + 1)) / maxPts, & i < k - 1 \end{cases} \end{aligned}

Time complexity O(k + maxPts), space complexity O(k + maxPts). Where k$ is the maximum score.

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 leq i leq 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.