[C++] One solution and two optimization with explanation
The idea:\nAs always, try to think recursively first, let P(i) return the probability of reaching i. Through the description of the question, we can deduce that
The idea:\nAs always, try to think recursively first, let `P(i)` return the probability of reaching `i`. Through the description of the question, we can deduce that `P(i) = P(i - 1) / maxpts + P(i - 2) / maxpts + ... + P(i - maxpts) / maxpts` where `0 <= i - whatever < k`. For the final answer all we need to do is just add up `P(k) + P(k + 1) + ... + P(n)`. Great! Let us implement this.\n\nImplementation 1:\n```\nclass Solution {\n    vector<double> mem;\n    double P(int i, int k, int maxPts) {\n        if(mem[i] != -1) {\n            return mem[i];\n        }\n        \n        mem[i] = 0;\n        for(int j = 1; j <= maxPts; j++) {\n            if(i - j >= 0 && i - j < k) mem[i] += P(i - j, k, maxPts) / maxPts;\n        }\n        \n        return mem[i];\n    }\n    \npublic:\n    double new21Game(int n, int k, int maxPts) {\n        if(k == 0 || k + maxPts <= n) return 1;\n        mem = vector<double>(n + 1, -1);\n        mem[0] = 1;\n        double ret = 0;\n        for(int i = k; i <= n; i++) {\n            ret += P(i, k, maxPts);\n        }\n        \n        return ret;\n    }\n};\n```\nThis solution works for most test cases, but eventually TLE. Hmmmm, before we start optimizing, let us first analyze the time complexity to have a basic idea of the upper bound we want to beat. There are a total of `n` unique cases, each case takes an average `O(n)`, this gives us the time complexity of `O(n^2)`\n\nOptimization 1(dp):\nOk, maybe we timed out because recursion calls takes slightly more time. I doubt it but you never know with leetcode. As with most memorization solutions, we can change this to a bottom up DP solution. \n```\nclass Solution {\npublic:\n    double new21Game(int n, int k, int maxPts) {\n        vector<double> dp(n + 1, 0);\n        double prob = 1.0/maxPts;\n        dp[0] = 1;\n        for(int i = 0; i < k; i++) {\n            double add = dp[i] * prob;\n            for(int j = i + 1; j <= n && j - i <= maxPts; j++) {\n                dp[j] += add;\n            }\n        }\n        \n        double sum = 0;\n        for(int i = k; i <= n; i++) {\n            sum += dp[i];\n        }\n        \n        return sum;\n    }\n};\n```\nNoticed that I changed a couple of things, instead of finding the solution backwards, we add to the solutions to the right of us. This actually does not change our recurrence relationship, I just find this way of implementation easier to write. The time complexity is still the same but we got rid of recursion so let us press submit and...TLE.\n\nOpimization 2(dp + sliding window):\nLet us revisit our recurrence relationship again...this is why I always love to write down the reccurence relationship before implementation just so that if we need to optimize we can look back to find some ideas from it. To remind you, our reccurence relationship is `P(i) = P(i - 1) / maxpts + P(i - 2) / maxpts + ... + P(i - maxpts) / maxpts`. Let\'s so some algebraic manipulation and get `P(i) = P(i - 1) / maxpts + P(i - 2) / maxpts + ... + P(i - maxpts) / maxpts = (P(i - 1) + P(i - 2) + ... + P(i - maxpts)) / maxpts`. Whenever you see this continuous pattern (aka subarrays) you should think sliding window. We are essentially getting the sum of an atmost `maxpts` sized sliding window and then dividing it by `maxpts`. Due to the nature of sliding window, we can reduce the running time to `O(n)`! Nice, let us implement.\n```\nclass Solution {\npublic:\n    double new21Game(int n, int k, int maxPts) {\n        if(k == 0 || k + maxPts <= n) return 1.0;\n        vector<double> dp(n + 1, 0);\n        dp[0] = 1;\n        int j = 0;\n        int i = 0;\n        double wsum = 0, res = 0;\n        while(j <= n) {\n            if(j < k) wsum += dp[j++];\n            else res += dp[j++];\n            if(j - i > maxPts) {\n                wsum -= dp[i++];\n            }\n            \n            if(j <= n) dp[j] = wsum / maxPts;\n        }\n        \n        return res;\n    }\n};\n```\nFinally, not more TLE. As before the time complexity is `O(n)` and the space complexity is `O(n)`.
[]