友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
808. 分汤
有 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 同时分配完的概率一半。返回值在正确答案 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 <= 109
思路分析
没想到竟然是动态规划！将想得到指定数量的解，那么可以从四种情况来获取：即减去对应数量的值。又因为每次操作都是 25 的倍数，所以，可以把原始数字除以 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
27
28
29
30
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-07-03 22:51:51
*/
public double soupServings(int n) {
if (n >= 4451) {
return 1;
}
n = (n + 24) / 25;
double[][] memo = new double[n + 1][n + 1];
return dfs(n, n, memo);
}
private double dfs(int a, int b, double[][] memo) {
if (a <= 0 && b <= 0) {
return 0.5D;
}
if (a <= 0) {
return 1;
}
if (b <= 0) {
return 0;
}
if (memo[a][b] != 0) {
return memo[a][b];
}
return memo[a][b] = (dfs(a - 4, b, memo) + dfs(a - 3, b - 1, memo)
+ dfs(a - 2, b - 2, memo) + dfs(a - 1, b - 3, memo)) / 4;
}