C++ 12ms O(K+W) solution with explanation
First, the destination conditional probability is P(<=N | >= K) which equals to P(<= N && >= K) / P(>=K).\n\nWithout limitations, \nP(x) = 1 / w * (P(x - 1) + P
First, the destination conditional probability is **P(<=N | >= K)** which equals to **P(<= N && >= K) / P(>=K)**.\n\nWithout limitations, \nP(x) = 1 / w * (P(x - 1) + P(x - 2) +... + P(x-w)) \n= 1 / w * sumP(x - w, x - 1)\n= **1 / w * sumP(lb, ub)**.\nHere, P(x) means the probability of becoming x points after some draws.\nlb, ub means lower bound and upper bound.\n\nBut there are some limitations to lb and ub:\n1. **lb >= 0**  (let P(0) = 1)\n2. **ub <= K - 1**, because when you have K points or more, you cannot draw a new card.\n\nTo calculate all the P()s is very time-consuming, thus we can use the cumulative sum technique.\n\nFinally, \nP(<= N && >= K) = sumP(K, N), and\nP(>= K) = sumP(K, +\u221E).\nIn fact, when x > K + W - 1, P(x) = 0, thus sumP(K, +\u221E) = sumP(K, K + W - 1);\nAlso, sumP(K, N) = sumP(K, min(N, K + W - 1))\n\nHere is my code:\n\n```\nclass Solution {\npublic:\n    double new21Game(int N, int K, int W) {\n        vector<double> sum(K + W); // cumulative sum\n        sum[0] = 1;\n        for (int i = 1; i <= K + W - 1; i++) {\n            int t = min(i - 1, K - 1);\n            if (i <= W) {\n                sum[i] = sum[i - 1] + sum[t] / W;\n            } else {\n                sum[i] = sum[i - 1] + max((sum[t] - sum[i - W - 1]) / W, 0.0);\n            }\n        }\n        double result = (sum[min(N, K + W - 1)] - sum[K - 1]) / (sum[K + W - 1] - sum[K - 1]);\n        return result;\n    }\n};\n```
[]