Java O(K) DP Solution, 21 ms
\nclass Solution {\n    public double new21Game(int N, int K, int W) {\n        if(K == 0)\n            return 1.0;\n        double[] preSum = new double[K+1];\
```\nclass Solution {\n    public double new21Game(int N, int K, int W) {\n        if(K == 0)\n            return 1.0;\n        double[] preSum = new double[K+1];\n        double currProb = 0.0;\n        for(int i = K-1; i >= 0; --i) {\n            int tmp = W - K +1 +i;\n            double subtractVal = 0.0;\n            if(tmp < 0){\n                subtractVal = preSum[K+tmp];\n                tmp = 0;\n            }\n            currProb = preSum[i+1]/W + ((double)Math.min(N-K+1, tmp))/W - subtractVal/W;\n            preSum[i] = currProb + preSum[i+1];\n        }\n        return currProb;\n    }\n}\n```
[]