题目分析

本题和上天讲过的香槟塔非常类似，也是模拟题，比香槟塔复杂一些，但是思路更清晰一些。小伙伴们想一想如何模拟呢？

记忆化

小伙伴们有没有想过，为什么不存在先分配100ml汤B的操作呢？

因为提供100ml汤B就和方案1对称，方案2和方案4对称，方案3自身对称，所以答案一定是0.5。

本题选择汤都是25的整数倍，不足25的也会被选择，因此就可以先将汤的容量除以25，并向上取整。A除以B上取整的简单写法是(A + B - 1) / B。因此n可以简化为(n + 24) / 25，记为k。

那么可知汤A可以选择k次，汤B也可以选择k次。每次有四种选择

0.25的概率让下一次A的数量变成A - 4，B的数量变成B
0.25的概率让下一次A的数量变成A - 3，B的数量变成B - 1
0.25的概率让下一次A的数量变成A - 2，B的数量变成B - 2
0.25的概率让下一次A的数量变成A - 1，B的数量变成B - 3

当A的数量小于等于0时，如果B的数量也小于等于0，则说明A和B同时分配完，返回0.5，当B的数量大于0，返回1。如果A的数量大于0，B的数量小于等于0，则返回0。

其他情况下说明都没有选择完，返回上面四种情况的概率之和 x 0.25

为了防止重复搜索，可以使用二维数组记录当前A和B剩余的数量，称为记忆化。

算法的时间复杂度为O(n^2)，空间复杂度为O(n^2)。

本题有一个小技巧，我们发现当n很大的时候(超过5000)，概率已经无限接近于1了，因此本题要求返回值误差在1e-5，即当n > 5000的时候，直接返回1即可。

如果全部暴力求解，会TLE，当以5000为上界时，n / 25 = 200，再计算平方，只需要40000次计算即可，完全是满足条件的。

class Solution {
    private double[][] mem;

    public double soupServings(int n) {
        if (n >= 6000) {
            return 1;
        }
        n = (n + 25 - 1) / 25;
        mem = new double[n + 1][n + 1];
        return dfs(n, n);
    }

    private double dfs(int a, int b) {
        if (a <= 0) {
            return b <= 0 ? 0.5: 1;
        }
        if (b <= 0) {
            return 0;
        }
        if (mem[a][b] == 0) {
            mem[a][b] = 0.25 * (dfs(a - 1, b - 3) + dfs(a - 2, b - 2) + dfs(a - 3, b - 1) + dfs(a - 4, b));
        }
        return mem[a][b];
    }
}

动态规划

能使用记忆化求解的题目，基本上都可以使用动态规划求解。

因为记忆化的本质是递归，所以一般都是从结果开始逆推。即A和B剩余的数量为m和n，第一次选择后，A和B剩余的数量是m1和n1，第二次选择时，剩余m2和n2，直到mk和nk小于等于0位置。

动态规划往往相反，A和B剩余的数量为m和n，概率能否由m1和n1递推得到呢？(m1 < m, n1 <= n)，m1和n1应该满足什么条件呢？

可得状态转移方程

$$ dp[i][j] = 0.25 * (dp[i - 1][j - 3] + dp[i - 2][j - 2] + dp[i - 3][j - 1] + dp[i - 4][j]) $$

算法的时间复杂度为O(n^2)，空间复杂度为O(n^2)。

class Solution {
    private double[][] dp;

    public double soupServings(int n) {
        if (n >= 6000) {
            return 1;
        }
        n = (n + 25 - 1) / 25;
        dp = new double[n + 1][n + 1];
        dp[0][0] = 0.5;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = 0.25 * (getP(i - 1, j - 3) + getP(i - 2, j - 2) + getP(i - 3, j - 1) + getP(i - 4, j));
            }
        }
        return dp[n][n];
    }

    private double getP(int a, int b) {
        if (a <= 0) {
            return b <= 0 ? 0.5 : 1;
        }
        if (b <= 0) {
            return 0;
        }
        return dp[a][b];
    }
}

刷题总结

记忆化和动态规划的本质是将原问题转化为性质相同的子问题，本题的原问题是有n份的A和n份的B，每一次可以使用pA和qB，使用后的子问题变成n - p份的A和n - q份的B，和原问题的问法相同，因此需要考虑记忆化和动态规划的算法。