Posted on 2023-07-29 18:07
Uriel 閱讀(57)
評論(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)