C++ top-bottom solution
according to the solution:\n\nf(x) = 1/W [f(x + 1) + f(x + 2) + ... + f(x + W)]            (1)\nf(x - 1) = 1/W [f(x) + f(x + 1) + ... + f(x + W - 1)]      (2)\n
according to the solution:\n\nf(x) = 1/W *[f(x + 1) + f(x + 2) + ... + f(x + W)]            (1)\nf(x - 1) = 1/W *[f(x) + f(x + 1) + ... + f(x + W - 1)]      (2)\n\n(2) - (1), we can get :\nf(x - 1) = f(x) - 1/W *[f(x + W) - f(x)                            (3)\n\nbut  in (3) equation, the x must less than K - 1, this is very important.\n\n![image](https://assets.leetcode.com/users/zackyne/image_1555774225.png)\n\n\n```c++\nclass Solution {\n    int N;\n    int K;\n    int W;\n    double fk;\n    vector<double> cache;\npublic:\n    double new21Game(int N, int K, int W) {\n        this->N = N;\n        this->K = K;\n        this->W = W;\n        fk = 1.0 / W * (min(N - K + 1, W));\n        cache = vector<double>(K + W, -1);\n        return f(0);\n    }\n    \n    double f(int x) {\n        if (x == K - 1) {\n            return fk;\n        }\n        \n        if (x >= K && x <= N) {\n            return 1.0;\n        }\n        \n        if (x > N) {\n            return 0;\n        }\n        \n        if (cache[x] != -1) {\n            return cache[x];\n        }\n        \n        double ans = f(x + 1) - 1.0 / W * (f(x + 1 + W) - f(x + 1));\n        cache[x] = ans;\n        return ans;\n    }  \n};\n```
[]