题目描述
leetcode 中等题
有 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：
1
2
3
4
5
6
| 输入: n = 50
输出: 0.62500
解释:如果我们选择前两个操作，A 首先将变为空。
对于第三个操作，A 和 B 会同时变为空。
对于第四个操作，B 首先将变为空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。
|
提示1：
分析
在该题的两个解法中，不论是自顶向下的记忆化搜索还是自底向上的动态规划，时间复杂度都是 $O(n^2)$，即使是将 $n$ 除以 $25$ （后面有解释），在该题的数据规模下仍然会 TLE。
我们可以发现，随着分配次数的增加，汤 A 比汤 B 先分配完的概率或者答案也是增大的。事实上，当 $n >= 4475$ 后，这个答案和 $1$ 的误差就已经小于题目容忍的误差了。所以当 $n < 4475$ 时，我们可以通过记忆化搜索或者动态规模得出答案，否则直接返回 $1$ 即可。
记忆化搜索
首先，由于数据规模较大以及四种分配操作都是 $25$ 的倍数，因此我们可以将 $n$ 除以 $25$（向上取整），并将四种分配操作变为 $(4, 0),(3, 1),(2, 2),(1, 3)$，且每种操作的概率均为 $0.25$。
递归求解，当要分给 $A$ 和 $B$ 的汤均小于等于 $0$ 时，依题意返回 $0.5$，当仅 $A$ 小于等于 $0$ 时依题意返回 $1$，仅 $B$ 小于等于 $0$ 时返回 $0$，其他情况递归求解四种情况下的平均值即可。
同时为了避免重复递归，使用 $cache[i][j]$ 保存 $A$ 剩余 $i$，$B$ 剩余 $j$ 时的结果。
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
27
28
29
30
31
32
| class Solution {
double[][] cache;
public double soupServings(int n) {
n= (int)Math.ceil((double)n / 25);
if(n >= 179){
return 1;
}
cache = new double[n + 1][n + 1];
return dfs(n, n);
}
private double dfs(int a, int b){
if(a <= 0 && b <= 0){
return 0.5;
}
if(a <= 0){
return 1;
}
if(b <= 0){
return 0;
}
if(cache[a][b] == 0){
double q = dfs(a - 4, b);
double w = dfs(a - 3, b - 1);
double e = dfs(a - 2, b - 2);
double r = dfs(a - 1, b - 3);
cache[a][b] = 0.25 * (q + w + e + r);
}
return cache[a][b];
}
}
|
动态规划
类似记忆化搜索的思路，可以转成动态规划求解。
定义 $dp(i, j)$ 表示 $A$ 剩余 $i$ 、 $B$ 剩余 $j$ 时的解，边界情况如同上面所解释的，非边界情况下转移方程为：
$$
\begin{align}
&dp(i, j) = \frac{1}{4} \times (dp(i - 4, j) + dp(i - 3, j - 1) + dp(i - 2, j - 2) + dp(i - 1, j - 3))\\
\end{align}
$$
需要注意的是在这道题中与记忆化搜索相比动态规划会多出一些无效状态的计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public double soupServings(int n) {
n = (n + 25 - 1) / 25;
if(n >= 179){
return 1;
}
double[][] dp = new double[n + 1][n + 1];
dp[0][0] = 0.5;
for (int i = 1; i <= n; i++) {
dp[0][i] = 1.0;
}
for(int i = 1; i < n + 1; i++){
for(int j = 1; j < n + 1; j++){
dp[i][j] += dp[Math.max(0, i - 4)][j] / 4;
dp[i][j] += dp[Math.max(0, i - 3)][j - 1] / 4;
dp[i][j] += dp[Math.max(0, i - 2)][Math.max(0, j - 2)] / 4;
dp[i][j] += dp[i - 1][Math.max(0, j - 3)] / 4;
}
}
return dp[n][n];
}
}
|