package leetcode;

/**
 * https://leetcode.com/problems/new-21-game/
 */
public class Problem837 {
    public double new21Game(int N, int K, int W) {
        return new21Game(N, K, W, 0);
    }

    private static double new21Game(int n, int k, int w, int val) {
        if (val >= k) {
            if (val <= n) {
                return 1;
            }
            return 0;
        }
        double sum = 0;
        for (int i = 1; i <= w; i++) {
            double p = new21Game(n, k, w, val + i) * (1.0 / w);
            sum += p;
        }
        return sum;
    }

    public static void main(String[] args) {
        Problem837 prob = new Problem837();
        System.out.println(prob.new21Game(10, 1, 10)); // 1.00000
        System.out.println(prob.new21Game(6, 1, 10)); // 0.60000
        System.out.println(prob.new21Game(21, 17, 10)); // 0.73278
        System.out.println(prob.new21Game(2, 2, 4)); // 0.3125
        System.out.println(prob.new21Game(10, 2, 10)); // 0.99
    }
}

@@ -139,24 +139,67 @@
 K, int W) %7B%0A
+        Double%5B%5D memo = new Double%5BN + 1%5D;%0A
         retu
@@ -221,16 +221,22 @@
  K, W, 0
+, memo
 );%0A    %7D
@@ -301,16 +301,31 @@
  int val
+, Double%5B%5D memo
 ) %7B%0A    
@@ -436,32 +436,105 @@
 rn 0;%0A        %7D%0A
+        if (memo%5Bval%5D != null) %7B%0A            return memo%5Bval%5D;%0A        %7D%0A
         double s
@@ -629,16 +629,22 @@
  val + i
+, memo
 ) * (1.0
@@ -694,439 +694,44 @@
     
-return sum;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem837 prob = new Problem837();%0A        System.out.println(prob.new21Game(10, 1, 10)); // 1.00000%0A        System.out.println(prob.new21Game(6, 1, 10)); // 0.60000%0A        System.out.println(prob.new21Game(21, 17, 10)); // 0.73278%0A        System.out.println(prob.new21Game(2, 2, 4)); // 0.3125%0A        System.out.println(prob.new21Game(10, 2, 10)); // 0.99
+memo%5Bval%5D = sum;%0A        return sum;
 %0A   

Solve problem 837