837. New 21 Game

T: O(min(n,k+w)) ⇒ ex3: O(27) 所以一般正常是 k+w, S也是, 除非 ex4, n 比較大, 就用n的

S: O(k+w)

class Solution {
    public double new21Game(int n, int k, int w) { // w = maxPts
        if (k == 0) {
            return 1.0;
        }
        
        double[] dp = new double[k+w]; // ex: 17+10 = 27
        for (int i = k; i <= n && i < k+w; i++) {
            dp[i] = 1.0;
        }
        
        dp[k-1] = 1.0*Math.min(n-k+1, w)/w; // 要1.0!
        for (int i = k-2; i >= 0; i--) {
            dp[i] = dp[i+1] - (dp[i+w+1] - dp[i+1])/w;
        }
        return dp[0];
    }
}

/*
f(i) = when k = i 時還能抽牌達成 <= n 的機率

    x. k                         k+w
15 16 17 18 19 20 21 22 23 24 25 26
    |  1. 1. 1. 1  1 0  0. 0. 0. 0
   can draw one more 
    f(16) = 1/10 * (1+1+1+1+1+0+0+0+0+0) = 0.5 = when k = 16 時還能抽1張牌能達成 <= n 的機率
          = 1/w * (f(17)+f(18)+f(19)...)
     f(x) = 1/w *(f(x+1)+f(x+2)+...f(x+w)) 

15 16 17 18 19 20 21 22 23 24 25 26
    |  1. 1. 1. 1  1 0  0. 0. 0. 0
         
f(15) = 1/10(抽一點) * f(16) + 1/10 * (5) = 0.55
f(x-1) = 1/w *(f(x)+f(x+1)+f(x+2)+...f(x+w-1)) 


f(x) = 1/w *(f(x+1)+f(x+2)+...f(x+w)) 
f(x-1) = 1/w *(f(x)+f(x+1)+f(x+2)+...f(x+w-1)) 

f(x) - f(x-1) = 1/w * (f(x+w) - f(x))
f(x-1) = f(x) - 1/w * (f(x+w) - f(x))
=> f(x) = f(x+1) - 1/w * (f(x+w+1) - f(x+1))

     
=>  dp[i] = dp[i+1] - 1/w*(dp[i+w+1] - dp[i+1]);
*/