0808. 分汤【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 记忆化搜索

1. 📝 题目描述

• leetcode

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

1. 从汤 A 取 100 毫升，从汤 B 取 0 毫升
2. 从汤 A 取 75 毫升，从汤 B 取 25 毫升
3. 从汤 A 取 50 毫升，从汤 B 取 50 毫升
4. 从汤 A 取 25 毫升，从汤 B 取 75 毫升

注意：

• 不存在从汤 A 取 0 ml 和从汤 B 取 100 ml 的操作。
• 汤 A 和 B 在每次操作中同时被取出。
• 如果一次操作要求你取出比剩余的汤更多的量，请取出该汤剩余的所有部分。

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

返回汤 A 在 B 前取完的概率，加上两种汤在 同一回合 取完概率的一半。返回值在正确答案 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
解释：
如果我们选择第一个操作，A 首先将变为空。
如果我们选择第二个操作，A 将在执行操作 [1, 2, 3] 时变为空，然后 A 和 B 在执行操作 4 时同时变空。
如果我们选择第三个操作，A 将在执行操作 [1, 2] 时变为空，然后 A 和 B 在执行操作 3 时同时变空。
如果我们选择第四个操作，A 将在执行操作 1 时变为空，然后 A 和 B 在执行操作 2 时同时变空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.71875。

---

提示：

• 0 <= n <= 10^9

2. 🎯 s.1 - 记忆化搜索

c

double memo[201][201];
bool visited[201][201];

double dp(int a, int b) {
    if (a <= 0 && b <= 0) return 0.5;
    if (a <= 0) return 1.0;
    if (b <= 0) return 0.0;
    if (visited[a][b]) return memo[a][b];
    visited[a][b] = true;
    memo[a][b] = 0.25 * (dp(a-4,b) + dp(a-3,b-1) + dp(a-2,b-2) + dp(a-1,b-3));
    return memo[a][b];
}

double soupServings(int n) {
    n = (n + 24) / 25;
    if (n >= 200) return 1.0;
    memset(visited, false, sizeof(visited));
    return dp(n, n);
}

js

/**
 * @param {number} n
 * @return {number}
 */
var soupServings = function (n) {
  n = Math.ceil(n / 25)
  if (n >= 200) return 1
  const memo = new Map()
  const dp = (a, b) => {
    if (a <= 0 && b <= 0) return 0.5
    if (a <= 0) return 1
    if (b <= 0) return 0
    const key = a * 201 + b
    if (memo.has(key)) return memo.get(key)
    const res =
      0.25 *
      (dp(a - 4, b) + dp(a - 3, b - 1) + dp(a - 2, b - 2) + dp(a - 1, b - 3))
    memo.set(key, res)
    return res
  }
  return dp(n, n)
}

py

class Solution:
    def soupServings(self, n: int) -> float:
        n = (n + 24) // 25
        if n >= 200:
            return 1.0
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def dp(a: int, b: int) -> float:
            if a <= 0 and b <= 0: return 0.5
            if a <= 0: return 1.0
            if b <= 0: return 0.0
            return 0.25 * (dp(a-4,b) + dp(a-3,b-1) + dp(a-2,b-2) + dp(a-1,b-3))
        return dp(n, n)

• 时间复杂度：$O(1)$，当 n >= 4800 时直接返回 1，否则状态数为常数级
• 空间复杂度：$O(1)$

算法思路：

• 将 n 缩放为 25 的倍数简化计算，四种操作变为 (4,0),(3,1),(2,2),(1,3)
• 当 n >= 4800 时概率足够接近 1.0，直接返回
• 对剩余小规模 n 使用记忆化搜索计算概率