837. New 21 Game

Version #4 Like version2 -> Sliding window
Bug -> edge case when K == 0, we should return 1.0

24.81 % 
class Solution {
    public double new21Game(int N, int K, int W) {
        if (K == 0 ||K + W <= N) return 1.0;
        // keep a window whose start is only W away from current i
        double[] dp = new double[N + 1];
        int left = 0;
        double sum = 1;
        dp[0] = 1;
        double result = 0;
        // [left, right)
        // prob of right is sum[left, right - 1]/W
        // if (right - left > W) -> sum -= left, left++
        // We stop adding to sum when right >= K
        // Adding to result when right >= K
        for (int right = 1; right <= N; right++) {
            if (right - left > W) {
                sum -= dp[left];
                left++;
            }
            dp[right] = sum / W;
         
            if (right < K) {
                sum += dp[right];
            } else {
                result += dp[right];
            }
        }
        return result;
    }
}

Version #2 DP like climbing stairs[Preferred]

78.98 % 
class Solution {
    public double new21Game(int N, int K, int W) {
if (K == 0 || N >= K + W) return 1;
// dp[i] -> the probability to get i points
// we can reach dp[i] from [i-W, i-1]
// sum(dp[i-W]/W + ... + dp[i-1]/W) -> sum(dp[i-W]...dp[i-1])/W
double[] dp = new double[N + 1];
double sumW = 1;
double result = 0.0;
// K .. N
dp[0] = 1;
for (int i = 1; i <= N; i++) {
dp[i] = sumW / W;
if (i >= K) {
result += dp[i];
} else {
sumW += dp[i];
}
if (i >= W) {
sumW -= dp[i - W];
}
}
return result;
}
}


Version #1 Backward DP with Queue

4.20 %
class Solution {
    public double new21Game(int N, int K, int W) {
// 0 ... K-1 K K+1 ... N .. K-1+W
Queue<Double> que = new LinkedList<>();
if (N < K) {
return 0.0;
}
double curr = K - 1 + W;
double sum = 0.0;
while (curr > N) {
que.offer(0.0);
curr--;
}
while (curr >= K) {
que.offer(1.0);
sum += 1.0;
curr--;
}
double result = 1.0;
while (curr >= 0) {
result = sum / W;
sum -= que.poll();
sum += result;
que.offer(result);
curr--;
}
return result;
}
}


Version #3 Naiive DP[TLE]
Time O(NW)

class Solution {
    public double new21Game(int N, int K, int W) {
        // stops when K <= points
        // accumulate the probablity of [K, N]
        double[] dp = new double[N + 1];
        dp[0] = 1;
        double result = 0;
        for (int i = 0; i <= N; i++) {
            if (i < K) { // keep drawing and add the possibility to i+x
                double prop = dp[i] / W;
                // we are having i points
                for (int x = 1; x <= W && i + x <= N; x++) {
                    dp[i + x] += prop;
                }
            } else { // we stop at here
                result += dp[i];
            }
        }
        return result;
    }
}