[Java] Clean O(K + W)-Time O(W)-Space Solution || with comments
The most basic solution, though TLE, explains everything clearer: \n\n\nclass Solution {\n    public double new21Game(int N, int K, int W) {\n        if (K == 0
The most basic solution, though TLE, explains everything clearer: \n\n```\nclass Solution {\n    public double new21Game(int N, int K, int W) {\n        if (K == 0) return 1.0;\n        \n        // dp[i] : prob of getting no more than N points when starting with i points\n        double[] dp = new double[K];\n        \n        for (int i = K-1; i >= 0; i--) {\n            for (int p = i + 1; p <= i + W; p++) {\n                if (p > N) {\n                    dp[i] += 0.0;\n                } else if (p >= K) {\n                    dp[i] += 1.0;\n                } else {\n                    dp[i] += dp[p];\n                }\n            }\n            \n            dp[i] /= W;\n        }\n        \n        return dp[0];\n    }\n}\n```\n\nWe can easily optimize the solution above to: \n```\nclass Solution {\n    public double new21Game(int N, int K, int W) {\n        if (K == 0) return 1.0;\n        \n        Deque<Double> queue = new LinkedList<>();\n        double sum = 0.0;\n        for (int i = K; i < K + W; i++) {\n            double prob = (i <= N) ? 1.0 : 0.0;\n            queue.offerLast(prob);\n            sum += prob;\n        }\n        \n        \n        for (int i = K - 1; i >= 0; i--) {\n            double prob = sum / W;\n            sum = sum - queue.pollLast() + prob;\n            queue.offerFirst(prob);\n        }\n        \n        return queue.peekFirst();\n    }\n}\n```
['Dynamic Programming', 'Queue', 'Java']