力扣-分汤

题目链接：https://leetcode.cn/problems/soup-servings/description/?envType=daily-question&envId=2025-08-08

题目

你有两种汤，A 和 B，每种初始为 n 毫升。在每一轮中，会随机选择以下四种服务操作中的一种，每种操作的概率为 0.25，且与之前的所有轮次 无关：

• 从汤 A 取 100 毫升，从汤 B 取 0 毫升

• 从汤 A 取 75 毫升，从汤 B 取 25 毫升

• 从汤 A 取 50 毫升，从汤 B 取 50 毫升

• 从汤 A 取 25 毫升，从汤 B 取 75 毫升
  注意：

• 不存在先分配 100 ml 汤B 的操作。

• 汤 A 和 B 在每次操作中同时被倒入。

• 如果一次操作要求你倒出比剩余的汤更多的量，请倒出该汤剩余的所有部分。

• 操作过程在任何回合中任一汤被用完后立即停止。

返回汤 A 在 B 前耗尽的概率，加上两种汤在 同一回合 耗尽概率的一半。返回值在正确答案 10^5 的范围内将被认为是正确的。

分析

首先由题目可知，不同的服务操作之间每次只差了25毫升，因此我们可以将每次操作除以25，来简化运算（必须要注意到的是，n也必须除以25）。将四种分配操作变为 (4,0),(3,1),(2,2),(1,3)，且每种操作的概率均为 0.25。

我们可以用动态规划来解决这个问题，设dp数组，dp(i,j)代表汤 A 和汤 B 分别剩下 i 和 j 份时所求的概率值，即汤 A 先分配完的概率 + 汤 A 和汤 B 同时分配完的概率除以 2 .
状态转移方程为：

此外在 n 非常大的时候，汤 A 会有很大的概率比 B 先分配完，汤 A 被先取完的概率应该非常接近 1。事实上，当我们进行实际计算时发现，当 n ≥ 4475 时，所求概率已经大于 0.99999 了（可以通过上面的动态规划方法求出），它和 1 的误差（无论是绝对误差还是相对误差）都小于 10^−5。实际我们在进行测算时发现：
n=4475,p≈0.999990211307
n=4476,p≈0.999990468596

因此在 n≥179×25 时，我们只需要输出 1 作为答案即可。在其它的情况下，我们使用动态规划计算出答案。

代码

/**
 * @param {number} n
 * @return {number}
 */
var soupServings = function(n) {
    n = Math.ceil(n / 25);
    if (n >= 179) {
        return 1.0;
    }
    const dp = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0));
    dp[0][0] = 0.5;
    for (let i = 1; i <= n; i++) {
        dp[0][i] = 1.0;
    }
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = (dp[Math.max(0, i - 4)][j] + dp[Math.max(0, i - 3)][Math.max(0, j - 1)] + dp[Math.max(0, i - 2)][Math.max(0, j - 2)] + dp[Math.max(0, i - 1)][Math.max(0, j - 3)]) / 4.0;
        }
    }
    return dp[n][n];
};