Fast 8-line JAVA O(N) solution
dp[i] stores possibility of getting i.\n\n\n    public double new21Game(int N, int K, int W) {\n        if (K == 0) return 1.0;\n        double[] dp = new doubl
dp[i] stores possibility of getting i.\n\n```\n    public double new21Game(int N, int K, int W) {\n        if (K == 0) return 1.0;\n        double[] dp = new double[K + W];\n        dp[0] = 1.0;\n        for (int i = 1; i <= Math.min(N, K + W - 1); i++) {\n            double pos = dp[Math.min(i - 1, K - 1)] - (i - W - 1 >= 0 ? dp[i - W - 1] : 0);\n            dp[i] = pos / W + dp[i - 1];\n        }\n        return dp[N] - dp[K - 1];\n    }\n```\n\nbased on TLE solution:\n\n```\n    public double new21Game(int N, int K, int W) {\n        double[] dp = new double[K + W];\n        dp[0] = 1.0;\n        for (int i = 1; i <= Math.min(N, K + W - 1); i++) {\n            double pos = 0;\n            for (int j = Math.max(0, i - W); j <= Math.min(i - 1, K - 1); j++) {\n                pos += dp[j];\n            }\n            dp[i] = pos / W;\n        }\n        double res = 0;\n        for (int i = K; i <= Math.min(N, K + W - 1); i++) {\n            res += dp[i];\n        }\n        return res;\n    }\n```
[]