Medium
题目描述
有两种汤：汤 A 和汤 B，每种汤初始时都有 n 毫升。在每一轮中，会随机选择以下四种操作中的一种，每种操作的概率都是 0.25，且与之前的操作无关：
- 倒出 100 毫升汤 A 和 0 毫升汤 B
- 倒出 75 毫升汤 A 和 25 毫升汤 B
- 倒出 50 毫升汤 A 和 50 毫升汤 B
- 倒出 25 毫升汤 A 和 75 毫升汤 B
注意：
- 没有操作会倒出 0 毫升汤 A 和 100 毫升汤 B
- 汤 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
约束：
- 0 <= n <= 10^9
提示：
- 对于大的 n，答案趋近于一个常数值
- 如果我们被允许执行许多操作而没有偏见，哪种汤更可能先耗尽？
解题思路
这是一个经典的动态规划概率问题。
核心思路：
状态定义：设
dp[a][b]表示当汤 A 剩余 a 毫升，汤 B 剩余 b 毫升时，满足题目要求的概率（A 先用完的概率 + 同时用完概率的一半）状态转移：根据四种操作，每种操作概率为 0.25：
- 操作1：倒出 (100, 0)
- 操作2：倒出 (75, 25)
- 操作3：倒出 (50, 50)
- 操作4：倒出 (25, 75)
边界条件：
- 如果 A 先用完：返回 1.0
- 如果 B 先用完：返回 0.0
- 如果同时用完：返回 0.5
优化技巧：
- 当 n 很大时（>= 5000），由于汤 A 消耗更快，答案趋近于 1.0
- 将状态空间缩放到 25 的倍数来减少计算量
- 使用记忆化搜索避免重复计算
时间复杂度优化：对于大的 n，我们观察到当 n >= 5000 时，由于汤 A 的消耗速度总体上比汤 B 快，所以答案会非常接近 1.0。
代码实现
class Solution {
public:
double soupServings(int n) {
if (n >= 5000) return 1.0;
// 将n转换为25的倍数来简化计算
n = (n + 24) / 25;
vector<vector<double>> memo(n + 1, vector<double>(n + 1, -1));
function<double(int, int)> dfs = [&](int a, int b) -> double {
if (a <= 0 && b <= 0) return 0.5; // 同时用完
if (a <= 0) return 1.0; // A先用完
if (b <= 0) return 0.0; // B先用完
if (memo[a][b] != -1) return memo[a][b];
memo[a][b] = 0.25 * (dfs(max(0, a-4), b) + // (100,0)/25
dfs(max(0, a-3), max(0, b-1)) + // (75,25)/25
dfs(max(0, a-2), max(0, b-2)) + // (50,50)/25
dfs(max(0, a-1), max(0, b-3))); // (25,75)/25
return memo[a][b];
};
return dfs(n, n);
}
};
class Solution:
def soupServings(self, n: int) -> float:
if n >= 5000:
return 1.0
# 将n转换为25的倍数来简化计算
n = (n + 24) // 25
memo = {}
def dfs(a, b):
if a <= 0 and b <= 0:
return 0.5 # 同时用完
if a <= 0:
return 1.0 # A先用完
if b <= 0:
return 0.0 # B先用完
if (a, b) in memo:
return memo[(a, b)]
memo[(a, b)] = 0.25 * (
dfs(max(0, a-4), b) + # (100,0)/25
dfs(max(0, a-3), max(0, b-1)) + # (75,25)/25
dfs(max(0, a-2), max(0, b-2)) + # (50,50)/25
dfs(max(0, a-1), max(0, b-3)) # (25,75)/25
)
return memo[(a, b)]
return dfs(n, n)
public class Solution {
public double SoupServings(int n) {
if (n >= 5000) return 1.0;
// 将n转换为25的倍数来简化计算
n = (n + 24) / 25;
double[,] memo = new double[n + 1, n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
memo[i, j] = -1;
}
}
return Dfs(n, n, memo);
}
private double Dfs(int a, int b, double[,] memo) {
if (a <= 0 && b <= 0) return 0.5; // 同时用完
if (a <= 0) return 1.0; // A先用完
if (b <= 0) return 0.0; // B先用完
if (memo[a, b] != -1) return memo[a, b];
memo[a, b] = 0.25 * (
Dfs(Math.Max(0, a-4), b, memo) + // (100,0)/25
Dfs(Math.Max(0, a-3), Math.Max(0, b-1), memo) + // (75,25)/25
Dfs(Math.Max(0, a-2), Math.Max(0, b-2), memo) + // (50,50)/25
Dfs(Math.Max(0, a-1), Math.Max(0, b-3), memo) // (25,75)/25
);
return memo[a, b];
}
}
var soupServings = function(n) {
if (n >= 5000) return 1.0;
// 将n转换为25的倍数来简化计算
n = Math.ceil(n / 25);
const memo = new Map();
function dfs(a, b) {
if (a <= 0 && b <= 0) return 0.5; // 同时用完
if (a <= 0) return 1.0; // A先用完
if (b <= 0) return 0.0; // B先用完
const key = a + ',' + b;
if (memo.has(key)) return memo.get(key);
const result = 0.25 * (
dfs(Math.max(0, a-4), b) + // (100,0)/25
dfs(Math.max(0, a-3), Math.max(0, b-1)) + // (75,25)/25
dfs(Math.max(0, a-2), Math.max(0, b-2)) + // (50,50)/25
dfs(Math.max(0, a-1), Math.max(0, b-3)) // (25,75)/25
);
memo.set(key, result);
return result;
}
return dfs(n, n);
};
复杂度分析
| 复杂度 | 大小 |
|---|---|
| 时间复杂度 | O(n²) |
| 空间复杂度 | O(n²) |
其中 n 是缩放后的汤量。由于我们对大于 5000 的 n 直接返回 1.0，实际的时间和空间复杂度都被限制在较小的范围内。