Java Sliding Window + DP Explanation
Was able to reach the basic DP solution on my own, but found the offical solutions explanation for the sliding window optimization pretty much incomprehensible 
Was able to reach the basic DP solution on my own, but found the offical solutions explanation for the sliding window optimization pretty much incomprehensible so thought I\'d give it a shot. \n\nBasically, as you should have already figured out if you are reading this, the **Prob[i]** represents that probability that starting from the current value in the game **i** you terminate the game with a value less than or equal to **K**. Since the game starts with the player having zero points if we want to calculate the probability for arriving at the end condition without exceeding **K** from the beginning of the game we need to calculate **Prob[0]**, simple enough. \n\nThe optimization comes from the insight that each time you are are calculating the next value **Prob[i - 1]** you are recomputing a sum that only differs slightly from what was needed to compute **Prob[i]**.\n\nBy maintaining this calculation we keep a running sum of the last W probabilities, which is exactly what we needed to calculate the current one and are now able to do it in constant time instead of O(W).\n\n\n\n```\n\n\nclass Solution {\n\n    public double new21Game(int N, int K, int W) {\n        double[] prob = new double[W + K];\n        double window = 0;\n        //Terminal Cases\n        for (int i = K + W - 1; i >= K; i--) {\n            prob[i] = (i <= N) ? 1 : 0;\n            window += prob[i];\n        }\n\n        //Count down\n        for (int i = K - 1; i >= 0; i--) {\n            prob[i] = window / W;\n            window += prob[i] - prob[i + W];\n        }\n\n        return prob[0];\n    }\n}\n```
[]