Java O(K + W) DP solution with explanation
Firstly I came up with a basic DP solution which cost O((K + W) * W) time and it runs TLE:\n\n\nclass Solution {\n    public double new21Game(int N, int K, int 
Firstly I came up with a basic DP solution which cost `O((K + W) * W)` time and it runs TLE:\n\n```\nclass Solution {\n    public double new21Game(int N, int K, int W) {\n        if (K == 0) {\n            return 1;\n        }\n        int max = K + W - 1;\n        double[] dp = new double[max + 1];\n        dp[0] = 1;\n        for (int i = 1; i <= max; i++) {\n            for (int j = 1; j <= W; j++) {\n                if (i - j >= 0 && i - j < K) {\n                    dp[i] += dp[i - j] / W;\n                }\n            }\n        }\n        double result = 0;\n        for (int i = K; i <= N; i++) {\n            result += dp[i];\n        }\n        return result;\n    }\n}\n```\n\nThen I realize that the transition equation `dp[i] = (dp[i - W] + dp[i - W + 1] + ... + dp[i - 1]) / W` could be simplified to `dp[i] = (sum[i - 1] - sum[i - W - 1]) / W`.\n\nFurthermore, if we use `dp[i]` to directly represent the `sum[i]`, we can get `dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - W - 1]) / W`. This equation takes us to the final `O(K + W)` solution. Just take care with the beginning and the end of the array.\n\n```\nclass Solution {\n    public double new21Game(int N, int K, int W) {\n        if (K == 0) {\n            return 1;\n        }\n        int max = K + W - 1;\n        double[] dp = new double[max + 1];\n        dp[0] = 1;\n        for (int i = 1; i <= max; i++) {\n            dp[i] = dp[i - 1];\n            if (i <= W) {\n                dp[i] += dp[i - 1] / W;\n            } else {\n                dp[i] += (dp[i - 1] - dp[i - W - 1]) / W;\n            }\n            if (i > K) {\n                dp[i] -= (dp[i - 1] - dp[K - 1]) / W;\n            }\n        }\n        return dp[N] - dp[K - 1];\n    }\n}\n```\n
[]