Python O(n) solution
It took me more than 30 minutes to figure out why I was "wrong" at Example 3...\n```class Solution:\n    def new21Game(self, N, K, W):\n        """\n        :ty
It took me more than 30 minutes to figure out why I was "wrong" at Example 3...\n```class Solution:\n    def new21Game(self, N, K, W):\n        """\n        :type N: int\n        :type K: int\n        :type W: int\n        :rtype: float\n        """\n        d=[0]*(K+max(W,N)+10)\n        for i in range(K,N+1):\n            d[i]=1\n        ms=N-K+1\n        for i in range(K-1,-1,-1):\n            d[i]=ms/W\n            ms+=d[i]-d[i+W]\n        return d[0]
[]