跳转至

808. 分汤

题目描述

有 A 和 B 两种类型 的汤。一开始每种类型的汤有 n 毫升。有四种分配操作：

  1. 提供 100ml 的 汤A 和 0ml 的 汤B 。
  2. 提供 75ml 的 汤A 和 25ml 的 汤B 。
  3. 提供 50ml 的 汤A 和 50ml 的 汤B 。
  4. 提供 25ml 的 汤A 和 75ml 的 汤B 。

当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为 0.25 的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。

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

需要返回的值： 汤A 先分配完的概率 +  汤A和汤B 同时分配完的概率 / 2。返回值在正确答案 10-5 的范围内将被认为是正确的。

 

示例 1:

输入: n = 50
输出: 0.62500
解释:如果我们选择前两个操作，A 首先将变为空。
对于第三个操作，A 和 B 会同时变为空。
对于第四个操作，B 首先将变为空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。

示例 2:

输入: n = 100
输出: 0.71875

 

提示:

  • 0 <= n <= 109​​​​​​​

解法

方法一：记忆化搜索

在这道题中，由于每次操作都是 \(25\) 的倍数，因此，我们可以将每 \(25ml\) 的汤视为一份。这样就能将数据规模缩小到 \(\left \lceil \frac{n}{25} \right \rceil\)。

我们设计一个函数 \(dfs(i, j)\)，表示当前剩余 \(i\) 份汤 \(A\) 和 \(j\) 份汤 \(B\) 的结果概率。

当 \(i \leq 0\) 并且 \(j \leq 0\) 时，表示两种汤都分配完了，此时应该返回 \(0.5\)；当 \(i \leq 0\) 时，表示汤 \(A\) 先分配完了，此时应该返回 \(1\)；当 \(j \leq 0\) 时，表示汤 \(B\) 先分配完了，此时应该返回 \(0\)。

接下来，对于每一次操作，我们都有四种选择，即：

  • 从 \(i\) 份汤 \(A\) 中取出 \(4\) 份，从 \(j\) 份汤 \(B\) 中取出 \(0\) 份；
  • 从 \(i\) 份汤 \(A\) 中取出 \(3\) 份，从 \(j\) 份汤 \(B\) 中取出 \(1\) 份；
  • 从 \(i\) 份汤 \(A\) 中取出 \(2\) 份，从 \(j\) 份汤 \(B\) 中取出 \(2\) 份；
  • 从 \(i\) 份汤 \(A\) 中取出 \(1\) 份，从 \(j\) 份汤 \(B\) 中取出 \(3\) 份；

每一种选择的概率都是 \(0.25\)，因此，我们可以得到：

\[ dfs(i, j) = 0.25 \times (dfs(i - 4, j) + dfs(i - 3, j - 1) + dfs(i - 2, j - 2) + dfs(i - 1, j - 3)) \]

记忆化搜索即可。

另外，我们发现在 \(n=4800\) 时，结果为 \(0.999994994426\)，而题目要求的精度为 \(10^{-5}\)，并且随着 \(n\) 的增大，结果越来越接近 \(1\)，因此，当 \(n \gt 4800\) 时，直接返回 \(1\) 即可。

时间复杂度 \(O(C^2)\)，空间复杂度 \(O(C^2)\)。本题中 \(C=200\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def soupServings(self, n: int) -> float:
        @cache
        def dfs(i: int, j: int) -> float:
            if i <= 0 and j <= 0:
                return 0.5
            if i <= 0:
                return 1
            if j <= 0:
                return 0
            return 0.25 * (
                dfs(i - 4, j)
                + dfs(i - 3, j - 1)
                + dfs(i - 2, j - 2)
                + dfs(i - 1, j - 3)
            )

        return 1 if n > 4800 else dfs((n + 24) // 25, (n + 24) // 25)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    private double[][] f = new double[200][200];

    public double soupServings(int n) {
        return n > 4800 ? 1 : dfs((n + 24) / 25, (n + 24) / 25);
    }

    private double dfs(int i, int j) {
        if (i <= 0 && j <= 0) {
            return 0.5;
        }
        if (i <= 0) {
            return 1.0;
        }
        if (j <= 0) {
            return 0;
        }
        if (f[i][j] > 0) {
            return f[i][j];
        }
        double ans
            = 0.25 * (dfs(i - 4, j) + dfs(i - 3, j - 1) + dfs(i - 2, j - 2) + dfs(i - 1, j - 3));
        f[i][j] = ans;
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    double soupServings(int n) {
        double f[200][200] = {0.0};
        function<double(int, int)> dfs = [&](int i, int j) -> double {
            if (i <= 0 && j <= 0) return 0.5;
            if (i <= 0) return 1;
            if (j <= 0) return 0;
            if (f[i][j] > 0) return f[i][j];
            double ans = 0.25 * (dfs(i - 4, j) + dfs(i - 3, j - 1) + dfs(i - 2, j - 2) + dfs(i - 1, j - 3));
            f[i][j] = ans;
            return ans;
        };
        return n > 4800 ? 1 : dfs((n + 24) / 25, (n + 24) / 25);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func soupServings(n int) float64 {
    if n > 4800 {
        return 1
    }
    f := [200][200]float64{}
    var dfs func(i, j int) float64
    dfs = func(i, j int) float64 {
        if i <= 0 && j <= 0 {
            return 0.5
        }
        if i <= 0 {
            return 1.0
        }
        if j <= 0 {
            return 0
        }
        if f[i][j] > 0 {
            return f[i][j]
        }
        ans := 0.25 * (dfs(i-4, j) + dfs(i-3, j-1) + dfs(i-2, j-2) + dfs(i-1, j-3))
        f[i][j] = ans
        return ans
    }
    return dfs((n+24)/25, (n+24)/25)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function soupServings(n: number): number {
    const f = new Array(200).fill(0).map(() => new Array(200).fill(-1));
    const dfs = (i: number, j: number): number => {
        if (i <= 0 && j <= 0) {
            return 0.5;
        }
        if (i <= 0) {
            return 1;
        }
        if (j <= 0) {
            return 0;
        }
        if (f[i][j] !== -1) {
            return f[i][j];
        }
        f[i][j] =
            0.25 * (dfs(i - 4, j) + dfs(i - 3, j - 1) + dfs(i - 2, j - 2) + dfs(i - 1, j - 3));
        return f[i][j];
    };
    return n >= 4800 ? 1 : dfs(Math.ceil(n / 25), Math.ceil(n / 25));
}

评论