Python DP, iterate on points rather than draw count. Should be a "hard" problem
dp(n) means the probability getting point "n" at any count of draws. \ne.g. when random number is 1~3, we have:\ndp(n)=dp(n-3)\(1/3)+dp(n-2)\(1/3)+dp(n-1)\*(1/3
dp(n) means the probability getting point "n" at any count of draws. \ne.g. when random number is 1~3, we have:\ndp(n)=dp(n-3)\\*(1/3)+dp(n-2)\\*(1/3)+dp(n-1)\\*(1/3)\nAnd this kind of sum can be optimized using sliding window sum.\n\nWe cannot iterate DP on draw count, because it is hard to decide when to stop iterating. Instead we iterate on the obtained point, because each point can be obtained by the dp value of previous points. \n\nThis problem should be "hard" rather than "medium".\n\n```\n    def new21Game(self, N: int, K: int, W: int) -> float:\n        if K==0 or K-1+W<=N:\n            return 1\n        dp=[1]+[0]*N\n        cursum=1\n        for i in range(1,N+1):\n            # dp[i]=sum(dp[max(0,i-W):min(i,K)])*(1/W)\n            dp[i]=cursum*(1/W)\n            if i<K:\n                cursum+=dp[i]\n            if i>=W:\n                cursum-=dp[i-W]\n        return sum(dp[K:])\n```
[]