难度：★★★★☆
类型：代数
方法：动态规划

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

题目

有 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。

示例:
输入: N = 50
输出: 0.625
解释:
如果我们选择前两个操作，A将首先变为空。对于第三个操作，A和B会同时变为空。对于第四个操作，B将首先变为空。
所以A变为空的总概率加上A和B同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。
注释:

0 <= N <= 10^9。
返回值在 10^-6 的范围将被认为是正确的。

解答

我们使用动态规划来解决这个问题。动态规划的思想是，把问题的整体划分成可以在有限次数循环进行的子问题，每个子问题都是容易解决的。

定义函数dp，功能是求取汤A和汤B各剩a和b时，按照题目要求的返回值。因此输入有两个，输出有一个。分汤不是没有截止的，分多少次也是不知道的，但是可以肯定的是，每当A汤或者B汤有一个被分完了，那就可以停止了。因此，在函数入口处就可以安置一个跳出条件，即当a或者b小于零时，返回根据题目要求计算的数值。

如果不满足跳出条件，则可以计算题目要求的概率了，计算的过程涉及到调用自身函数dp。

这里有两点可以注意：

1. 题目的分汤数是以25为基数的，可以通过将25看做一份来简化表达。
2. 为了避免重复计算，可以设置字典用于存储已经计算过的情况。

class Solution(object):
    def soupServings(self, N):
        Q, R = divmod(N, 25)
        N = Q + (R > 0)
        if N >= 500:
            return 1

        seen = dict()

        def dp(a, b):
            if (a, b) not in seen:
                if a <= 0 or b <= 0:            # 如有一种汤用完
                    if a <= 0 and b <= 0:       # 如果两种汤同时用完
                        ans = 0.5
                    elif a <= 0:                # 如果汤A用完
                        ans = 1.0
                    else:                       # 如果汤B用完
                        ans = 0.0
                else:
                    ans = sum([dp(a - 4, b), dp(a - 3, b - 1), dp(a - 2, b - 2), dp(a - 1, b - 3)]) / 4
                seen[(a, b)] = ans
            return seen[(a, b)]

        return dp(N, N)

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析