分汤

难度: 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 <= 10⁹

Submission

运行时间: 32 ms

内存: 17.6 MB

class Solution:
    # def soupServings(self, n: int) -> float:
    #     n_a = (n + 24) // 25
    #     n_b = (n + 24) // 25
    #     def target(n_a, n_b):
    #         if n_a <= 0 and n_b <= 0:
    #             return 0.5
    #         if n_a <= 0 and n_b > 0:
    #             return 1
    #         if n_a > 0 and n_b <= 0:
    #             return 0
    #         else:
    #             return 0.25*( target(n_a-4, n_b) + target(n_a-3, n_b-1) + target(n_a-2, n_b-2) + target(n_a-1, n_b-3))
        
    #     if n > 4800:
    #         return 1.0
    #     else:
    #         return target(n_a, n_b)
    def soupServings(self, n: int) -> float:
        n = (n + 24) // 25
        if n >= 179:
            return 1.0
        @cache
        def dfs(a: int, b: int) -> float:
            if a <= 0 and b <= 0:
                return 0.5
            if a <= 0:
                return 1.0
            if b <= 0:
                return 0.0
            return (dfs(a - 4, b) + dfs(a - 3, b - 1) +
                    dfs(a - 2, b - 2) + dfs(a - 1, b - 3)) / 4
        return dfs(n, n)

Explain

这个题解采用了记忆化搜索（动态规划的一种形式）来解决问题。首先，将毫升数转换为以25毫升为单位的较小值以简化计算。当汤的量n足够大时（n>=179），直接返回1.0，因为在这种情况下，几乎总是汤A会先分配完或者与汤B同时分配完。对于较小的n，使用深度优先搜索(DFS)递归地计算四种分配操作的概率，使用装饰器cache来存储已计算的结果，避免重复计算。最终的概率由四个递归调用的平均值决定，分别对应四种不同的操作。递归的边界条件处理了汤A或汤B先分配完以及同时分配完的情况。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def soupServings(self, n: int) -> float:
        # 将n转换为以25为单位，以简化问题规模
        n = (n + 24) // 25
        # 当n大于等于179时，可以近似认为概率为1
        if n >= 179:
            return 1.0
        # 使用缓存装饰器来存储已计算的结果，避免重复计算
        @cache
        def dfs(a: int, b: int) -> float:
            # 如果a和b都不足以继续任何操作，返回0.5
            if a <= 0 and b <= 0:
                return 0.5
            # 如果只剩下a不足，返回1
            if a <= 0:
                return 1.0
            # 如果只剩下b不足，返回0
            if b <= 0:
                return 0.0
            # 递归计算所有可能操作的平均概率
            return (dfs(a - 4, b) + dfs(a - 3, b - 1) +
                    dfs(a - 2, b - 2) + dfs(a - 1, b - 3)) / 4
        # 返回最终计算的概率
        return dfs(n, n)

Explore

在n大于等于179时，可以近似认为概率为1.0的原因基于数学实验和统计模拟的结果。随着n的增加，汤A和汤B被同时分配完的概率迅速减少，而汤A被分配完的概率趋近于1。因此，当n的值较大时，几乎总是汤A会先分配完或者与汤B同时分配完，使得结果趋近于1.0。虽然这个结论缺乏严格的数学证明，但通过大量模拟实验可以观察到这一趋势。

`@cache`装饰器是一种优化技术，属于动态规划的记忆化部分，用于自动存储已经计算过的函数结果。当函数被再次调用时，如果输入参数相同，装饰器会直接返回缓存中的结果，而不是重新计算。这样可以显著减少重复计算，提高算法的执行效率。在递归过程中，尤其是处理有大量重叠子问题的递归调用时，使用`@cache`可以极大地减少计算量，从而降低时间复杂度。

在递归函数`dfs`中，当`a <= 0 and b <= 0`时返回0.5，代表了汤A和汤B同时分配完的情况。这种情况下，我们不能确定是汤A先分配完还是汤B先分配完，因此中立地返回0.5，代表这两种可能性的平均概率。这是一种简化处理，用于在同时耗尽两种汤时给出一个合理的概率估计，反映了同时耗尽的不确定性。