题目描述
有 A 和 B 两种类型 的汤。一开始每种类型的汤有 n 毫升。有四种分配操作：
- 提供
100ml 的 汤A 和 0ml 的 汤B 。
- 提供
75ml 的 汤A 和 25ml 的 汤B 。
- 提供
50ml 的 汤A 和 50ml 的 汤B 。
- 提供
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
提示:
解法
方法一：记忆化搜索
在这道题中，由于每次操作都是 $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$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | 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);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | 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));
}
|