难度: Medium
原题连接
内容描述
There are two types of soup: type A and type B. Initially we have N ml of each type of soup. There are four kinds of operations:
Serve 100 ml of soup A and 0 ml of soup B
Serve 75 ml of soup A and 25 ml of soup B
Serve 50 ml of soup A and 50 ml of soup B
Serve 25 ml of soup A and 75 ml of soup B
When we serve some soup, we give it to someone and we no longer have it. Each turn, we will choose from the four operations with equal probability 0.25. If the remaining volume of soup is not enough to complete the operation, we will serve as much as we can. We stop once we no longer have some quantity of both types of soup.
Note that we do not have the operation where all 100 ml's of soup B are used first.
Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time.
Example:
Input: N = 50
Output: 0.625
Explanation:
If we choose the first two operations, A will become empty first. For the third operation, A and B will become empty at the same time. For the fourth operation, B will become empty first. So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.
Notes:
0 <= N <= 10^9.
Answers within 10^-6 of the true value will be accepted as correct.
思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******
毫无疑问A被消耗的概率大于B被消耗的概率，所以当N越大时，最终结果就越靠近1，我们需要测出这个threhold
这里参考两篇post
前者说threhold是4800，后者用数学证明算出threshold是5650
剩下的就是记忆化搜索+DFS了，beats 55.10%
因为当N大于某个数的时候我们就直接返回1了，所以时间复杂度和空间复杂度都是O(1)
class Solution:
def soupServings(self, N):
"""
:type N: int
:rtype: float
"""
self.cache = {}
def helper(a, b):
if (a, b) in self.cache:
return self.cache[(a,b)]
if a <= 0 and b <= 0: # A, B become empty at the same time
return 0.5
if a <= 0 or b <= 0: # if A becoming empty first, return 1; else return 0
return 1 if a < b else 0
self.cache[(a,b)] = 0.25 * (helper(a-100, b) + helper(a-75, b-25) + \
helper(a-50, b-50) + helper(a-25, b-75))
return self.cache[(a,b)]
return N > 5650 and 1 or helper(N, N)