C++ Beats 100% DP with Simple Explanation
Approach\nIt\'s fairly clear this question will have to be DP, since it\'s similar to \'count number of ways to reach i\', but instead we\'re counting the proba
# Approach\nIt\'s fairly clear this question will have to be DP, since it\'s similar to \'count number of ways to reach i\', but instead we\'re counting the probabilities to reach i. So our dp will be\n\ndp[i] = probability of reaching i. (not quite, but it\'s a good way to think about it)\n\nTherefore, our solution will be the sum of all dp[k..n] probabilities, since we are going to overshoot k every time! We shouldn\'t count any numbers before k since those are not numbers we are going to END on.\n\nNow the way to do is to just have a DP state where we calculate the probabilities forward from the state we are currently on. E.g. if I am on number i with probability 0.5, I know there is a 0.5 * (1/maxPts) probability that any of the 1..maxPts numbers ahead of me will be chosen. \n\nTo set dp[i + 1..maxPts] we can either use a loop in O(n), or use a line sweep in O(1). Of course, we choose the faster one.\n\nThen just keep a running prefix sum and when you are on i, that running sum will be the probability of dp[i]. So dp[i] isn\'t the probability, it\'s the line sweep array, which is close enough :)\n\nNote: we set dp[0] = 1.0, dp[1] = -1.0 because we will always start from 0, so it\'s 100%. The -1 is to reduce the probability back down after we propagate the probability of 0 onwards.\n\n# Code\n```\nclass Solution {\npublic:\n    static constexpr int mx = (int)1e4 + 5;\n    double dp[mx];\n    double new21Game(int n, int k, int maxPts) {\n        dp[0] = 1.0;\n        dp[1] = -1.0;\n        double run = 0;\n        for (int i = 0; i < k; i++) {\n            run += dp[i];\n            if (i+1 <= n) dp[i+1] += run / maxPts;\n            if (i+maxPts+1 <= n) dp[i+maxPts+1] -= run / maxPts;\n        }\n        double ans = 0;\n        for (int i = k; i <= n; i++) {\n            run += dp[i];\n            ans += run;\n        }\n        return ans;\n    }\n};\n\n```
['C++']