Question

808. 分汤

English Version

题目描述

有 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$。

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)

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;
  }
}

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);
  }
};

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)
}

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));
}