C++ 4ms,12lines solution with ONLY ONE line key code
Here is some explanation of my code.\n\nvector<double> p[i]  saves result possibility when the number starts at i, and p[0] is the final result.\n(p[l, r] is th
**Here is some explanation of my code.**\n\n```vector<double> p[i]```  saves result possibility when the number starts at ```i```, and ```p[0]``` is the final result.\n(```p[l, r]``` is the slice between ```p[l]``` and ```p[r]```)\n\nWe all know that when variable ```i``` near the target ```K``` or ```N```, ```p[i]``` is easy to calculate.\n\nLet\'s look at the *sample 3*:  ``` N = 21, K = 17, W = 10```\n\n**First ,```p[N, K] = p[17,21] = 1.0```, there is no doubt.**\n**Also ```p[i] = 0.0, i > N```**\n\nSecond, calculate the ```p[K - 1] = p[16]```,  it\'s easy:\n```p[K - 1] = (N - K + 1) / (double)W = (21 - 17 + 1) / 10.0 = 0.5```\n\nAnd last(which is also the most important iterate step), to calculate ```p[i], 0 < i < K - 1```, use the basic probability formula ,we have:\n**P[i] = sum(p[i  + 1, i + W]) / W**\n\n\n**If we use this formula directly, we get a method of *O\uFF08K * W)***\n\nNotice that:\n```p[i] = sum(p[i + 1], p[i + W]) / W```\n```p[i + 1] = sum(p[i + 2], p[i + W + 1]) / W```\nso\uFF0C```p[i] - p[i + 1] = (p[i + 1] - p[i + W + 1]) / W```  (**KEY formula**)\nTherefore, we can use the new formula to update every ```p[i]``` in *O(1)* time complexity.\n\nThe 12 line code shows below:\n\n```\nclass Solution {\npublic:\n    double new21Game(int N, int K, int W) {\n        if (K == 0) return 1.0;\n        vector<double> p(K + W + 1, 0.0);\n        for (int i = K; i <= N; ++i) {\n            p[i] = 1.0;\n        }\n        p[K - 1] = (N - K + 1) / (double)W;\n        for (int i = K - 2; i >= 0; --i) {\n            p[i] = p[i + 1]  + (p[i + 1] - p[i + 1 + W]) / W; \n        }\n        return p[0];\n    }\n};\n```
[]