808. Soup Servings 分汤

 1    double[][] memo = new double[200][200];//使用数组来缓存已经计算过的结果，进而在递归中剪枝。
 2    public double soupServings(int N) {
 3        // 技巧，(N+24)/25 进而将25，50，75，100 缩减到 1，2，3，4. 从而减少memo的使用
 4        return N >= 5000 ?  1.0 : getProbability((N + 24) / 25, (N + 24) / 25);
 5    }
 6
 7    //返回A为aml, B为bml情况下，A先空以及AB同时为空的概率之和。
 8    private double getProbability(int a, int b) {
 9        if (a <= 0 && b <= 0) return 0.5;// A和B同时为空的概率的一半。这里<0意味着不够serve
10        if (a <= 0) return 1;// A为空的概率为1
11        if (b <= 0) return 0;// B不可能在A不空的情况下为空。
12        if (memo[a][b] > 0) return memo[a][b];// 若之前出现过就直接从数组里拿，即记忆的功能
13
14        //当前阶段，分别选择4个operation中的某一个operation，进入下一层迭代。
15        memo[a][b] = 0.25 * (getProbability(a - 4, b) + getProbability(a - 3, b - 1) + getProbability(a - 2, b - 2) + getProbability(a - 1, b - 3));
16        return memo[a][b];
17    }