Python DP linear time clear deduction based on equation
Update: now the description has been updated, the same approach still applies. It is actually using sliding window implicitly. Suppose dp[i] represents the prob
*Update: now the description has been updated, the same approach still applies. It is actually using sliding window implicitly. Suppose dp[i] represents the prob with start with i points.*\nThen \n\n  dp[i] = 1/maxPts * (dp[i+1] + dp[i+2] + ... + dp[i+maxPts])\ndp[i+1] = 1/maxPts * (          dp[i+2] + ... + dp[i+maxPts] + dp[i+maxPts + 1])\n\n*It is obvious that if we do dp backward, moving from i+1 to i, most of the elments in the sliding window keep the same, except the first and last elements. That\'s where sliding window comes in.*\n\n*A more straightforward way is to just calculate dp[i+1] - dp[i], then it tells formula for dp[i], which can be directly used in code (this is a useful trick: simplify dp equations by looking at difference, which implicitly utilizing sliding window); below old post shows this approach. Both approaches actually the same in essence.*\n\nBased on the solution, \n![image](https://assets.leetcode.com/users/images/c579ebe1-a9e8-438c-94c4-86140e1f55b0_1615955371.8868845.png)\nNote that this holds only for x < K (for x>= K we can preset the value to 1.0 or 0.0).\nI got TLE by only using the above recursion function.\nActually based on it we have\nf(x) - f(x-1) = 1/W * ( f(x+W) - f(x) ), holds for x < K.\nthat is:\nf(x-1) = f(x) - 1/W( f(x+W) - f(x) ), for x < K.\n\nBased on this recurision relationship, we can directly have the following solution, without using any other variables or sliding windows.\n\n```\nclass Solution:\n    def new21Game(self, N: int, K: int, W: int) -> float:\n        if K == 0:\n            return 1.0\n        \n        # dp[i] = 1/W * dp[i+j] for j in range [1, W]\n        \n        dp = [0] * (K + W)\n        for i in range(K, N+1):\n            dp[i] = 1.0            \n        \n        # note that dp[K-1] need to compute seperately\n        for i in range(1, W+1):\n            dp[K-1] += 1/W * dp[K-1+i]\n        \n\t\t# starting from K-2, since the recusion needs x < K, and here x is i+1, so i < K-1\n        for i in range(K-2, -1, -1):\n            dp[i] = dp[i+1] - 1/W * (dp[i+1+W]-dp[i+1])\n                \n        return dp[0]
['Dynamic Programming', 'Sliding Window', 'Python3']