C++ DP O(K) time and space
Build an array dp such that dp[i] == new21Game(N-K+i+1, i+1, W), so that dp[K-1] == new21Game(N,K,W).\ndp[i] can be computed from dp[i-1], ..., dp[i-W] because 
Build an array dp such that `dp[i] == new21Game(N-K+i+1, i+1, W)`, so that `dp[K-1] == new21Game(N,K,W)`.\n`dp[i]` can be computed from `dp[i-1], ..., dp[i-W]` because of the following formula:\n![image](https://assets.leetcode.com/users/alreadydone/image_1559020627.png)\nThis is because:\nFrom the initial state 0, we have 1/W probability jumping to each state between 1 and W. If W >= K, then W-K+1 of these states are terminal (>=K), and min(W,N)-K+1 of them lie between K and N, yielding a probability of (min(W,N)-K+1)/W.\nFor any of remaining states `i` that is between 1 and K-1, we consider its probability of being <= N when first reaching a state that is >=K. But that is same as the probability of being <= N-i when first reaching a state that is >=K-i, which is `new21Game(N-i,K-i,W)`.\n\nIn the code below, `total` denotes the running summations in the above formula.\n\nRuntime: 4 ms, faster than 97.62% of C++ online submissions for New 21 Game.\nMemory Usage: 10.9 MB, less than 88.89% of C++ online submissions for New 21 Game.\n```\nclass Solution {\npublic:\n    double new21Game(int N, int K, int W) {\n        if (K == 0) return 1.0;\n        vector<double> dp(K);\n        auto total = 0.0;\n        for (auto i = 0; i < K; ++i) {\n            if (i < W) dp[i] = (total + min(N-K+1,W-i)) / W;\n            else dp[i] = total / W, total -= dp[i-W];\n            total += dp[i];\n        }\n        return dp[K-1];\n    }\n};\n```
[]