808. 分汤(Python)
难度:★★★★☆
类型:代数
方法:动态规划
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
题目
有 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。
这里有两点可以注意:
- 题目的分汤数是以25为基数的,可以通过将25看做一份来简化表达。
- 为了避免重复计算,可以设置字典用于存储已经计算过的情况。
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解决方案,请移步力扣中等题解析