One Pass DP O(N)
Intuition:\nThe same problems as "Climbing Stairs" or "Fibo Sequence".\n\n## Explanation:\ndp[i] is the probability that we get points i at some moment.\nIn ano
## **Intuition**:\nThe same problems as "Climbing Stairs" or "Fibo Sequence".\n\n## **Explanation**:\n`dp[i]` is the probability that we get points `i` at some moment.\nIn another word:\n`1 - dp[i]`is the probability that we skip the points `i`.\n\nThe do equation is that:\n`dp[i] = sum(last W dp values) / W`\n\nTo get `Wsum = sum(last W dp values)`,\nwe can maintain a sliding window with size at most `W`.\n<br>\n\n## **Time Complexity**:\nTime `O(N)`\nSpace `O(N)`, can be improve to `O(W)`\n<br>\n\n**C++:**\n```cpp\n    double new21Game(int N, int K, int W) {\n        if (K == 0 || N >= K + W) return 1.0;\n        vector<double> dp(N + 1);\n        dp[0] = 1.0;\n        double Wsum = 1.0, res = 0.0;\n        for (int i = 1; i <= N; ++i) {\n            dp[i] = Wsum / W;\n            if (i < K) Wsum += dp[i]; else res += dp[i];\n            if (i - W >= 0) Wsum -= dp[i - W];\n        }\n        return res;\n    }\n```\n\n**Java:**\n```java\n    public double new21Game(int N, int K, int W) {\n        if (K == 0 || N >= K + W) return 1;\n        double dp[] = new double[N + 1],  Wsum = 1, res = 0;\n        dp[0] = 1;\n        for (int i = 1; i <= N; ++i) {\n            dp[i] = Wsum / W;\n            if (i < K) Wsum += dp[i]; else res += dp[i];\n            if (i - W >= 0) Wsum -= dp[i - W];\n        }\n        return res;\n    }\n```\n**Python:**\n```py\n    def new21Game(self, N, K, W):\n        if K == 0 or N >= K + W: return 1\n        dp = [1.0] + [0.0] * N\n        Wsum = 1.0\n        for i in range(1, N + 1):\n            dp[i] = Wsum / W\n            if i < K: Wsum += dp[i]\n            if i - W >= 0: Wsum -= dp[i - W]\n        return sum(dp[K:])\n```
[]