<p>Alice plays the following game, loosely based on the card game <strong>&quot;21&quot;</strong>.</p>

<p>Alice starts with <code>0</code> points and draws numbers while she has less than <code>k</code> points. During each draw, she gains an integer number of points randomly from the range <code>[1, maxPts]</code>, where <code>maxPts</code> is an integer. Each draw is independent and the outcomes have equal probabilities.</p>

<p>Alice stops drawing numbers when she gets <code>k</code> <strong>or more points</strong>.</p>

<p>Return the probability that Alice has <code>n</code> or fewer points.</p>

<p>Answers within <code>10<sup>-5</sup></code> of the actual answer are considered accepted.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 10, k = 1, maxPts = 10
<strong>Output:</strong> 1.00000
<strong>Explanation:</strong> Alice gets a single card, then stops.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 6, k = 1, maxPts = 10
<strong>Output:</strong> 0.60000
<strong>Explanation:</strong> Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 21, k = 17, maxPts = 10
<strong>Output:</strong> 0.73278
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= k &lt;= n &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= maxPts &lt;= 10<sup>4</sup></code></li>
</ul>

# Understanding
# 1. Draw cards where each card is [1, maxPts] points
# 2. Stop drawing card when total points is greater/equal to k
# 3. What's the probability of having total points less/equal to n
#
# Algorithm
# 1. Consider a table.
#    - curr: current total point you have.
#    - prob: starting from 'curr', the probability of finishing with [k, n] total points.
# 
# 2. When curr is [k, ]
#    - the probability is 1.0 if curr <= n.
#    - the probability is 0.0 if n < curr.
#
# 3. The max point you can earn is k-1+maxPts by drawing 'maxPts' card when curr is 'k-1'
#
# 4. Now assume that you earned 'N' points so far. (curr = N)
#    You can draw 1 more card to reach ['N+1', 'N+maxPts'] points.
#    If you know probabilities for ['N+1', 'N+maxPts'], you can easily get probability fo 'N' as well.
#    
#          <----- possible next points ----->
#    'N' | 'N+1' 'N+2' 'N+3'  ...  'N+maxPts' 
#    prob('N') = [prob('N+1') + prob('N+2') + ... + prob('N+maxPts')] / 'maxPts'
#
# 5. With the approach above, calculate the sum of prob for ['K', 'K-1+maxPts']
# 6. Slide to the right until you reach prob('0'), which is the answer
#
class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0:
            return 1.0

        prob = {} # prob[x] = probability when curr is x
        
        # Compute the first window
        # - Calculate the sum of prob for ['K', 'K-1+maxPts']
        probSum = 0
        for i in range(k, k+maxPts):
            if i <= n:
                probSum += 1.0

        # Slide window to the left
        for curr in range(k-1, -1, -1):
            prob[curr] = probSum / maxPts

            # Update the window
            probSum += prob[curr]
            if (curr+maxPts) in prob:
                probSum -= prob[curr + maxPts]
            else:
                probSum -= 1.0 if curr + maxPts <= n else 0.0
        
        return prob[0]


17600