0808. 分汤

ITCharge大约 3 分钟

---

0808. 分汤

标签：数学、动态规划、概率与统计
难度：中等

题目链接

0808. 分汤 - 力扣

题目大意

描述：

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

从汤 A 取 100 毫升，从汤 B 取 0 毫升
从汤 A 取 75 毫升，从汤 B 取 25 毫升
从汤 A 取 50 毫升，从汤 B 取 50 毫升
从汤 A 取 25 毫升，从汤 B 取 75 毫升

注意：

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

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

要求：

返回汤 A 在 B 前取完的概率，加上两种汤在「同一回合」取完概率的一半。返回值在正确答案 $10^{-5}$ 的范围内将被认为是正确的。

说明：

$0 \le n \le 10^{9}$ 。

示例：

示例 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。

解题思路

思路 1:动态规划 + 记忆化搜索

定义 $dp(a, b)$ 表示汤 A 剩余 $a$ 毫升、汤 B 剩余 $b$ 毫升时,满足条件的概率。

状态转移:

如果 $a \le 0$ 且 $b \le 0$ ,返回 $0.5$ (同时取完)
如果 $a \le 0$ ,返回 $1$ (A 先取完)
如果 $b \le 0$ ,返回 $0$ (B 先取完)
否则: $dp(a, b) = 0.25 \times [dp(a-100, b) + dp(a-75, b-25) + dp(a-50, b-50) + dp(a-25, b-75)]$

优化:

由于每次操作都是 25 的倍数,可以将 $n$ 除以 25 来缩小规模。
当 $n$ 很大时( $n \ge 5000$ ),概率会非常接近 1,可以直接返回 1。

思路 1:代码

class Solution:
    def soupServings(self, n: int) -> float:
        # 当 n >= 5000 时,概率非常接近 1
        if n >= 5000:
            return 1.0
        
        # 将 n 转换为以 25 为单位(向上取整)
        n = (n + 24) // 25
        
        # 记忆化搜索
        memo = {}
        
        def dp(a, b):
            # 如果已经计算过,直接返回
            if (a, b) in memo:
                return memo[(a, b)]
            
            # 边界条件
            if a <= 0 and b <= 0:
                return 0.5
            if a <= 0:
                return 1.0
            if b <= 0:
                return 0.0
            
            # 状态转移
            result = 0.25 * (
                dp(a - 4, b) +      # 操作 1: A 取 100ml, B 取 0ml
                dp(a - 3, b - 1) +  # 操作 2: A 取 75ml, B 取 25ml
                dp(a - 2, b - 2) +  # 操作 3: A 取 50ml, B 取 50ml
                dp(a - 1, b - 3)    # 操作 4: A 取 25ml, B 取 75ml
            )
            
            memo[(a, b)] = result
            return result
        
        return dp(n, n)

思路 1:复杂度分析

时间复杂度: $O(n^2)$ ,其中 $n$ 是转换后的汤的容量。需要计算 $O(n^2)$ 个状态。
空间复杂度: $O(n^2)$ ,记忆化搜索需要存储 $O(n^2)$ 个状态。