初始A，B兩種湯都有n ml，每次可以執(zhí)行如下四種操作之一，輸出A先喝完的概率*1+AB同時(shí)喝完的概率*0.5，精度10^-5，遞歸+DP，但直接做會(huì)超過迭代深度，參考Discussion發(fā)現(xiàn)由輸出精度可以推算n大于某個(gè)值的時(shí)候可以直接輸出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)