【2022-11-21每日一题】808. 分汤[Medium]
2022-11-21
3分钟阅读时长
2022-11-21每日一题：808. 分汤
难度：Medium
标签：数学 、 动态规划 、 概率与统计
有 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
提示:
0 <= n <= 109
方法一：记忆化搜索
func soupServings(n int) float64 {
// n=4800 时，结果为 0.999994994426，而题目要求的精度为 10^−5，
// 并且随着 n 的增大，结果越来越接近 1，因此，当 n>4800 时，直接返回 1 即可
if n > 4800 {
return 1.0
}
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)
}
// 写法二
func soupServings(n int) float64 {
n = (n + 24) / 25 // 向上取整
if n >= 179 {
return 1
}
dp := make([][]float64, n+1)
for i := range dp {
dp[i] = make([]float64, n+1)
}
var dfs func(int, int) float64
dfs = func(a, b int) float64 {
if a <= 0 && b <= 0 {
return 0.5
}
if a <= 0 {
return 1
}
if b <= 0 {
return 0
}
dv := &dp[a][b]
if *dv > 0 {
return *dv
}
res := (dfs(a-4, b) + dfs(a-3, b-1) +
dfs(a-2, b-2) + dfs(a-1, b-3)) / 4
*dv = res
return res
}
return dfs(n, n)
}
复杂度分析
- 时间复杂度：O(C^2)。
- 空间复杂度：O(C^2)。
方法二：动态规划
func soupServings(n int) float64 {
n = (n+24)/25 // 向上取整
if n >= 179 {
return 1.0
}
dp := make([][]float64, n + 1)
for i := range dp {
dp[i] = make([]float64, n + 1)
}
// 当满足 i>0,j=0，此时无法再分配，而汤 A 还未分配完成，汤 A 永远无法完成分配，此时dp(i,j)=0
// 当满足 i=0,j=0，此时汤 A 和汤 B 同时分配完的概率为 1.0，汤 A 先分配完的概率为 0，因此 dp(i,j)=1.0×0.5=0.5
dp[0][0] = 0.5
for i := 1; i <= n; i++ {
// 当满足 i=0,j>0，此时无法再分配，汤 A 先分配完的概率为 1.0，汤 B 永远无法完成分配，因此 dp(i,j)=1.0；
dp[0][i] = 1.0
}
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
dp[i][j] = (dp[max(0,i-4)][j]+dp[max(0,i-3)][max(0,j-1)]+dp[max(0,i-2)][max(0,j-2)]+dp[max(0,i-1)][max(0,j-3)])/4 // 除以4， 相当于 * 0.25
}
}
return dp[n][n]
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
复杂度分析
- 时间复杂度：O(C^2)。
- 空间复杂度：O(C^2)。