Python 3 - Memorize DFS from O(KW+W) to O(K + W)
Intuiatively, we can generate the following equation:\n#### F(x) = (F(x+1) + F(x+2) + ... + F(x+W)) / W\nWhere F(x) is the prob that we will eventually have <= 
Intuiatively, we can generate the following equation:\n#### F(x) = (F(x+1) + F(x+2) + ... + F(x+W)) / W\nWhere F(x) is the prob that we will eventually have <= N points when we have x points.\nWe will stop picking when we have >= K points, so the exit of the recursion is `cur >= K`.\nThere are K+W states in total and for each state < K, we spend O(W) (the for loop) to generate the prob, therefore O(KW+W) in total.\n```\nclass 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        return self.dfs(N, K, W, 0, {})\n    \n    def dfs(self, N, K, W, cur, memo):\n        \n        if cur >= K:\n            return 1.0 if cur <= N else 0\n        \n        if cur in memo:\n            return memo[cur]\n        \n        prob = 0\n        \n        for i in range(1, W+1):\n            prob += self.dfs(N, K, W, cur+i, memo)\n        \n        prob /= W\n        \n        memo[cur] = prob\n        \n        return prob\n```\n\nHowever, do we really need a for loop to get the prob?\nSince \n#### F(x) = (F(x+1) + F(x+2) + ... + F(x+W)) / W\n#### F(x+1) = (F(x+2) + F(x+3) + ... + F(x+1+W)) / W\nAfter a substraction, we have \n#### F(x) = F(x+1) - 1/W * (F(x+1+W) - F(x+1))\nIn this case, we get our prob at **points = x** by a simple substraction which is O(1).\nHere we still have K + W states so the time complexity should be O(K+W).\n\n\n### But Wait...\nWhy does the exit or the base case of the recursion change..?\nThat\'s because the expression \n#### F(x) = F(x+1) - 1/W * (F(x+1+W) - F(x+1))\nrelies on the fact that for every F(x), we have:\n#### F(x) = (F(x+1) + F(x+2) + ... + F(x+W)) / W\nBut that is not true. \n#### In fact, when x = K, F(x) = either 1 or 0, but not (F(x+1) + ... + F(x+W)) / W\nSince the rule does not apply for F(K), we can not use the formula to calculate F(K-1)....\nAnd that is why we modify the base case here.\nAt x = K-1, only one more pick left, therefore we have two cases:\n\n1. N-(K-1) >= W, which means we pick all 1 to W safely.\n2. N-(K-1) < W, means that some of the numbers will make our points > N. Then we can only pick N-(K-1) from 1 to W.\n\nThe prob is therefore ```min(N-K+1, W) / W```\n```\nclass 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        return self.dfs(N, K, W, 0, {})\n    \n    def dfs(self, N, K, W, cur, memo):\n        \n        if cur == K-1:\n            return min(N-K+1, W) / W\n        if cur > N:\n            return 0\n        elif cur >= K:\n            return 1.0\n        \n        if cur in memo:\n            return memo[cur]\n        \n        prob = self.dfs(N, K, W, cur+1, memo) - (self.dfs(N, K, W, cur+1+W, memo) - self.dfs(N, K, W, cur+1, memo)) / W\n        \n        memo[cur] = prob\n        \n        return prob\n```
[]