<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>

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if n == 0 or k == 0:
            return 1.0
        
        
        dp = [0] * (n+1)
        dp[0] = 1.0

        lSumDP = [0] * (n+1)
        lSumDP[0] = 1.0

        for i in range(1, n+1):
            if i <= maxPts:
                if i >= k:
                    dp[i] = lSumDP[k-1] * (1/maxPts)
                else:
                    dp[i] = lSumDP[i-1] * (1/maxPts)
                lSumDP[i] = lSumDP[i-1] + dp[i]
                continue
            
            if i < k:
                diff = lSumDP[i-1]
                if i-maxPts-1 >= 0:
                    diff -= lSumDP[i-maxPts-1]
                
                dp[i] = diff * (1/maxPts)
                lSumDP[i] = lSumDP[i-1] + dp[i]
                continue
            
            if i >= k and i-maxPts <= k-1:
                print(i)
                diff = lSumDP[k-1]
                if i-maxPts-1 >= 0:
                    diff -= lSumDP[i-maxPts-1]
                
                dp[i] = diff * (1/maxPts)
                lSumDP[i] = lSumDP[i-1] + dp[i]
                continue

        ans = 0
        for i in range(k, n+1):
            ans += dp[i]

        print(dp)
        return ans


## in-efficient
# class Solution:
#     def new21Game(self, n: int, k: int, maxPts: int) -> float:
#         if n == 0 or k == 0 or n == k:
#             return 1.0
        
        
#         dp = [0] * (n+1)
#         dp[0] = 1.0

#         self.dp = dp
#         self.k = k
#         self.n = n
#         self.maxPts = maxPts
        
#         for i in range(0, k):
#             self.new21GameUtil(i)

#         ans = 0
#         print(self.dp)
#         for i in range(k, n+1):
#             ans += self.dp[i]
#         return ans

#     def new21GameUtil(self, start):
#         if start >= self.k:
#             return 0
        
#         for i in range(1, self.maxPts+1):
#             nxt = start+i
#             if nxt <= self.n:
#                 self.dp[nxt] += self.dp[start] * (1/self.maxPts)
        
            
17900