O(N) dp solution from uwi, with explanation
A intuitive idea is simply use dp[i] as the probability to reach i, dp[i]=probability[i].\n\nThen dp[i]=sum(dp[i-j]) for j in [1, W], but this causes O(KW) comp
A intuitive idea is simply use `dp[i]` as the probability to reach `i`, `dp[i]=probability[i]`.\n\nThen `dp[i]=sum(dp[i-j]) for j in [1, W]`, but this causes O(KW) complexity.\n\nIn uwi\'s code, \n\n`dp[i]` is the prefix for numbers larger than or equal to i, so `probability[i]=sum(dp[:i+1])`\n\nLet\'s use `p[i]` for `probability[i]`.\n\nIn this case,\n\n**the initial situation** is `p[0]=1, p[i]=0 for i>0`, so `dp[0]=1, dp[1]=-1`\n**the recursive formula** at `i` is to update `p[i+1:i+W+1]` only, so set `dp[i+1]+=p[i]/W, dp[i+W+1]-=p[i]/W`, and `p[i]` is maintained in the code as `val`.\n\nSo just add `val` for `i in range(K, N+1)`.\n\nHere is my python version:\n\n```\nclass Solution:\n    def new21Game(self, N, K, W):\n        dp = [0]*(N+3)\n        dp[0] = 1\n        dp[1] = -1\n        val = 0\n        \n        for i in range(K):\n            val += dp[i]\n            if i+1<=N:\n                dp[i+1] += val/W\n            if i+W+1<=N:\n                dp[i+W+1] -= val/W\n        ret = 0\n        for i in range(K, N+1):\n            val += dp[i]\n            ret += val\n\n        return ret\n```
[]