A python O(KW) solution and improved O(K) solution with explanation
The idea is from back to front.\nLet\'s consider the base case, if current sum is K-i, the probability of next sum to be inside [K,N] is min(N+1-K, i+W+1-K).\n\
The idea is from back to front.\nLet\'s consider the base case, if current sum is `K-i`, the probability of next sum to be inside `[K,N]` is `min(N+1-K, i+W+1-K)`.\n\nIn the `O(KW)` solution, `s[i]` is the probility of starting from this point, the probability to be inside `[K,N]`. So we divide into two cases, \n\nthe first case is it can directly jump into `[K,N]`, so first sum up from `i+1` to `K` and sum the posibility of jump inside `[K,N]`.\nthe second case is only can jump into non-[K,N] area.\n\n```python\nclass Solution(object):\n    # from a O(K*W) dp to a O(N) dp\n    def new21Game(self, N, K, W):\n        if K < 1:\n            return 1\n        if N>K+W:\n            return 0\n        \n        s = [0] * K\n        delta = 1.0/W \n        for i in range(K-1, -1, -1):\n            if (i + W) >= K:\n                for j in range(i+1,K):\n                    s[i]+=delta*s[j]\n\n                s[i] += min((i+W+1-K), (N+1-K)) *delta\n            else:\n                for j in range(i+1, i+W+1):\n                    s[i] += delta*s[j]\n        \n        return s[0]\n```\nThe `O(K)` solution is easy to figure it out. We add a `postSum` array, where `postSum[i]` means the sum of probability of jump from any point [i,K-1], the probability of result inside `[K,N]`. It is hard to understand, but I mean, it is just an array to keep the sum in previous solution, so we can use \n`postSum[i+1]- (postSum[i+W+1])` to represent the sum between `i+1` and `i+W+1`.\n\n```python\nclass Solution(object):\n    # from a O(K*W) dp to a O(N) dp\n    def new21Game(self, N, K, W):\n        if K == 0:\n            return 1\n        postSum = [0] * (K+1)\n        delta = 1.0/W \n        curr = 0\n        for i in range(K-1, -1, -1):\n            if (i + W) >= K:\n                curr = postSum[i+1] * delta + min((i+W+1-K), (N+1-K)) *delta\n                postSum[i] = postSum[i+1] + curr \n            else:\n                curr = postSum[i+1]*delta - (postSum[i+W+1])*delta\n                postSum[i] = postSum[i+1] + curr\n        \n        return curr\n```
[]