Posted on 2023-07-29 18:07
Uriel 阅读(28)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
数学 、
递归 & 分治 、
闲来无事重切Leet Code
初始A，B两种汤都有n ml，每次可以执行如下四种操作之一，输出A先喝完的概率*1+AB同时喝完的概率*0.5，精度10^-5，递归+DP，但直接做会超过迭代深度，参考Discussion发现由输出精度可以推算n大于某个值的时候可以直接输出1
1 #808
2 #Runtime: 36 ms (Beats 100%)
3 #Memory: 17 MB (Beats 79.25%)
4
5 class Solution:
6 def soupServings(self, n: int) -> float:
7 if n >= 4276:
8 return 1.0
9 @lru_cache(None)
10 def dp(x, y):
11 if x <= 0 and y > 0:
12 return 1
13 if x <= 0 and y <= 0:
14 return 0.5
15 if x > 0 and y <= 0:
16 return 0
17 return (dp(x - 100, y) + dp(x - 75, y - 25) + dp(x - 50, y - 50) + dp(x - 25, y - 75)) * 0.25
18
19 return dp(1.0 * n, 1.0 * n)