[Python3] top-down & bottom-up dp
Algo \nDefine fn(n) as the probability of points between K and N, i.e. [K, N] given existing point n. Then, \n\n1) if n < K, fn(n) = 1/W*(fn(n+1) + fn(n+2) + ..
Algo \nDefine `fn(n)` as the probability of points between `K` and `N`, i.e. `[K, N]` given existing point `n`. Then, \n\n1) if `n < K`, `fn(n) = 1/W*(fn(n+1) + fn(n+2) + ... + fn(n+W))`;\n2) if `K <= n <= N`, `fn(n) = 1`;\n3) if `N < n`, `fn(n) = 0`. \n\nTrick: if `n+1 < K`, then from \n`fn(n) = 1/W*(fn(n+1) + fn(n+2) + ... + fn(n+W))`\n`fn(n+1) = 1/W*(fn(n+2) + fn(n+3) + ... + fn(n+W+1))`\none can derive `fn(n) = (1+W)/W*fn(n) - 1/W*fn(n+W+1)`. When `n+1 == K`, this trick cannot be applied as the relationship of `fn(n+1) = 1/W*(fn(n+2) + ...)` doesn\'t hold in general. \n\nTop-down implementation (244ms, 5.39%)\n```\nclass Solution:\n    def new21Game(self, N: int, K: int, W: int) -> float:\n        \n        @lru_cache(None)\n        def fn(n): \n            """Return prob of of points between K and N given current point n."""\n            if N < n: return 0\n            if K <= n: return 1\n            if n+1 < K: return (1+W)/W*fn(n+1) - 1/W*fn(n+W+1)\n            return 1/W*sum(fn(n+i) for i in range(1, W+1))\n        \n        return fn(0)\n```\n\nBottom-up implementation (52ms, 99.67%)\n```\nclass Solution:\n    def new21Game(self, N: int, K: int, W: int) -> float:\n        ans = [0]*K + [1]*(N-K+1) + [0]*W\n        val = sum(ans[K:K+W])\n        for i in reversed(range(K)): \n            ans[i] = val/W\n            val += ans[i] - ans[i+W]\n        return ans[0]\n```
['Python3']