『LeetCode』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同时分配完的概率 / 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 <= 10^{9}\)

题解

【分汤】记忆化搜索与概率论剪枝

记忆化搜索

这题其实挺有意思的，最为关键的点其实是 返回值在正确答案 \(10^{-5}\) 的范围内将被认为是正确的 这句话。

可以简单分析一下，四种操作中，操作 2 和操作 4 是对称的，而操作 3 是平均分配，因此若是只有这三种操作那么两种汤被分配的概率应该是 0.5, 0.5, 但实际上我们还有操作 1 只分配 A 而不分配 B，这个操作会导致 A 汤被先分配完的概率大于 B 先分配完或者同时分配完的概率而且随着 \(n\) 增大这个概率是趋于 1 的，但关键的是题目给出了一个精确值的范围，也就是说当概率大于 \(1 - 10^{-5}\) 时可以直接返回 1，不能想到 \(n\) 增大到一个临界值时我们可以直接说概率就是 1，而这个临界值可以使用后面的记忆化搜索的方法推导出为精确值为 4450.

至于小于临界值的则需要单独计算，想象一下每一步有四种操作，那么爆搜的复杂度是 \(O(4^k)\) 其中 \(k\) 是最大操作次数，显然是不合要求的，但不难发现爆搜中有很多重复的操作，最简单的就是 2, 3, 4 操作次数相同，那么 A,B 是一样多的，所以加入记忆化后可以大大降低时间消耗

# Code language: Python
class Solution:
    def soupServings(self, n: int) -> float:
        if n >= 5000:
            return 1.
        
        @cache
        def dfs(a, b):
            if a <= 0 and b <= 0:
                return 0.5
            elif a <= 0:
                return 1.
            elif b <= 0:
                return 0.
            else:
                return 0.25 * dfs(a - 100, b) + 0.25 * dfs(a - 75, b - 25) + 0.25 * dfs(a - 50, b - 50) + 0.25 * dfs(a - 25, b - 75)

        # # 推算临界值
        # for i in range(1000, 1000000):
        #     if 1 - dfs(i, i) <= 1e-5:
        #         print(i)
        #         break
        
        return dfs(n, n)

时间复杂度: \(O(\min (n^2, 5000))\), 为什么是 \(n^2\) 呢？因为 \(A\) 汤剩余量最多为 \(n\), B 汤同理，那么总的状态数量为 \(n^2\), 所以记忆化搜索上界也是 \(O(n^2)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』808 分汤

题目

标签

题解

记忆化搜索