A setp by setp explanation
This question takes me a while to understand what this means.\n\nAfter struggled for a while, I would like to post how I understand if you are confused about wh
This question takes me a while to understand what this means.\n\nAfter struggled for a while, I would like to post how I understand if you are confused about what happened even after reading some of the solutions posted here.\n\nTake one example first: \n\nN = 12, W = 10, K = 10\n\nThe stop range for the game is [10, 10 + 10 -1] which is [K, K + W -1]\n\ndp[i] means if the target K is set to this one what is the possiblty to be <=N\n\nFor i <= W\ndp[0] = 1.0 for sure\n\ndp[1] = 1.0 / W because one of W chance we get 1\n\ndp[2] = dp[1]  / W + 1 / W we have 2 ways to get 2 here, 1 + 1 and 0 + 2\n\ndp[3] = dp[2] / W + 1 / W\n\nand so on, we can see this is a GP until i reach W, so dp[i] = (dp[i-1] + 1.0) / 2\n\nTo reach value i which is bigger than W, you must start from some previous value i in range [i - w, i - 1], so the possibilty smaller than that is not possible\n\nFor example i = 11, previous value range is [1, 10], but there is no such part of 1/W because no value of single draw can be > W, so we don\'t do the addition here. Instead, we need to reduce the change of value 1 after move to next value\n\ndp[11] = dp[1] + dp[2] ... + dp[10]\n\ndp[12] = dp[2] + d[3] ... + dp[10]\n\nEverytime we move to the next, get rid of the leftmost value.\n\nThe function stops at reach N.\n\nHere we use a Wsum to carry the sum to the next dp everytime.\n\nAnd the values end in range\n[10, min(10 + 10 -1, N)] will be the result\n\nHope this helps.\n\n```\nclass Solution:\n    """\n    @param N: int\n    @param K: int\n    @param W: int\n    @return: the probability\n    """\n    def new21Game(self, N, K, W):\n        # Write your code here.\n        if K == 0 or N >= K + W: \n            return 1.0\n        dp = [1.0] + [0.0] * N\n        Wsum = 1.0\n        for i in range(1, N + 1):\n            dp[i] = Wsum / W\n            if i < K: \n                Wsum += dp[i]\n            if i - W >= 0: \n                Wsum -= dp[i - W]\n        return sum(dp[K:])\n```\n
['Dynamic Programming', 'Python3']