LeetCode 题解工作台
分汤
你有两种汤， A 和 B ，每种初始为 n 毫升。在每一轮中，会随机选择以下四种操作中的一种，每种操作的概率为 0.25 ，且与之前的所有轮次 无关 ： 从汤 A 取 100 毫升，从汤 B 取 0 毫升 从汤 A 取 75 毫升，从汤 B 取 25 毫升 从汤 A 取 50 毫升，从汤 B 取 5…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
在这道题中，由于每次操作都是 的倍数，因此，我们可以将每 的汤视为一份。这样就能将数据规模缩小到 $\left \lceil \frac{n}{25} \right \rceil$。 我们设计一个函数 $dfs(i, j)$，表示当前剩余 份汤 和 份汤 的结果概率。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
你有两种汤，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 的范围内将被认为是正确的。
示例 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 <= 109
解题思路
方法一：记忆化搜索
在这道题中，由于每次操作都是 的倍数，因此，我们可以将每 的汤视为一份。这样就能将数据规模缩小到 。
我们设计一个函数 ，表示当前剩余 份汤 和 份汤 的结果概率。
当 并且 时，表示两种汤都分配完了，此时应该返回 ；当 时，表示汤 先分配完了，此时应该返回 ；当 时，表示汤 先分配完了，此时应该返回 。
接下来，对于每一次操作，我们都有四种选择，即：
- 从 份汤 中取出 份，从 份汤 中取出 份；
- 从 份汤 中取出 份，从 份汤 中取出 份；
- 从 份汤 中取出 份，从 份汤 中取出 份；
- 从 份汤 中取出 份，从 份汤 中取出 份；
每一种选择的概率都是 ，因此，我们可以得到：
记忆化搜索即可。
另外，我们发现在 时，结果为 ，而题目要求的精度为 ，并且随着 的增大，结果越来越接近 ，因此，当 时，直接返回 即可。
时间复杂度 ，空间复杂度 。本题中 。
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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(1) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Watch for floating-point accumulation errors in probability sums.
- question_mark
Notice if the candidate considers naive simulation versus DP state modeling.
- question_mark
Check understanding of stopping conditions and tie probabilities.
常见陷阱
外企场景- error
Ignoring half probability when both soups empty simultaneously.
- error
Failing to memoize overlapping DP states leading to exponential recursion.
- error
Incorrectly handling state transitions when soup quantities drop below zero.
进阶变体
外企场景- arrow_right_alt
Change serving sizes or probabilities to test flexible DP modeling.
- arrow_right_alt
Ask for probability that soup B empties first instead of A.
- arrow_right_alt
Introduce more soups or more complex serving patterns to extend state space.