Python DP solution explained
python\n"""\nThis code gives TLE but is easier to explaine, see the second code below for a no-TLE version\n"""\nclass Solution:\n    def new21Game(self, n: int
```python\n"""\nThis code gives TLE but is easier to explaine, see the second code below for a no-TLE version\n"""\nclass Solution:\n    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n\t\t# each index in dp stores the probability that, starting from this index, the final points <= n\n        dp=[0]*(k+1)\n\t\t# if we start from k, we do not have the next draw, and the result is always <= n\n        dp[k]=1\n        for idx in range(k-1,-1,-1):\n\t\t\t# two cases, 1) jumps to a next point that is <= k, then we can use the probability at the next point\n            for right in range(idx+1,min(k+1,idx+maxPts+1)):\n                dp[idx]+=dp[right]/maxPts\n            \n\t\t\t# 2) jumps to range (k, n]\n            if idx+maxPts>k:\n                dp[idx]+=(min(idx+maxPts,n)-k)/maxPts\n                \n        return dp[0]\n```\n\n```python\n"""\nThis version optimizes the sum and avoids TLE.\n"""\nclass Solution:\n    def new21Game(self, n: int, k: int, maxPts: int) -> float:\n        dp=[0]*(k+1)\n        dp[k]=1\n\t\t# keep track of the sum of dp from index to end\n        sum_to_end=[0]*(len(dp)+1)\n        sum_to_end[-2]=1\n        \n        for idx in range(k-1,-1,-1):\n\t\t\t# use the difference of sum instead\n            dp[idx]+= (sum_to_end[idx+1]-sum_to_end[min(k+1,idx+maxPts+1)])/maxPts\n            \n            if idx+maxPts>k:\n                dp[idx]+=(min(idx+maxPts,n)-k)/maxPts\n            \n            sum_to_end[idx]=sum_to_end[idx+1]+dp[idx]\n                \n        return dp[0]\n```
['Math', 'Dynamic Programming', 'Python']