[leetcode] 808. Soup Servings

[leetcode] 808. Soup Servings

Description

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 BServe 75 ml of soup A and 25 ml of soup BServe 50 ml of soup A and 50 ml of soup BServe 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.

分析

题目的意思是：这道题给了两种汤，A和B，开始时各给了N毫升的。然后说是有下面四种操作：

供应100毫升A汤，0毫升B汤。供应75毫升A汤，25毫升B汤。供应50毫升A汤，50毫升B汤。供应25毫升A汤，75毫升B汤。

选择每种操作的概率是一样的，求A汤供应完的概率加上A汤和B汤同时供应完一半的概率。

先来看这四种操作，由于概率相同，所以每一种操作都的有，所以这四种操作可以想象成迷宫遍历的周围四个方向，那么可以用递归来做。再看一下题目中给的N的范围，可以到10的9次方，而每次汤的消耗最多不过100毫升，由于纯递归基本就是暴力搜索，所以需要加上记忆数组memo，来避免重复运算，提高运行的效率。另外，汤的供应量都是25的倍数，所以可以将25毫升当作一份汤的量，所以这四种操作就变成了：

供应4份A汤，0份B汤。供应3份A汤，1份B汤。供应2份A汤，2份B汤。供应1份A汤，3份B汤。

所以汤份数就是可以通过除以25来获得，由于N可能不是25的倍数，会有余数，但是就算不到一份的量，也算是完成了一个操作，所以可以直接加上24再除以25就可以得到正确的份数。首先判断如果两种汤都没了，那么返回0.5，因为题目中说了如果两种汤都供应完了，返回一半的概率；如果A汤没了，返回1；如果B汤没了，返回0；如果上面的情况都没有进入，说明此时A汤和B汤都有剩余，所以先查记忆数组memo，如果其大于0，说明当前情况已经被计算过了，直接返回该值即可。如果没有的话，就要计算这种情况的值，通过对四种情况分别调用递归函数中，将返回的概率值累加后除以4即可。

代码

class Solution { public: double soupServings(int N) { if(N>10000) return 1; vector> memo(400,vector(400,0.0)); return solve((N+24)/25,(N+24)/25,memo); } double solve(int a,int b,vector> &memo){ if(a<=0&&b<=0){ return 0.5; } if(a<=0){ return 1.0; } if(b<=0){ return 0.0; } if(memo[a][b]>0) return memo[a][b]; memo[a][b]=0.25*(solve(a-4,b,memo)+solve(a-3,b-1,memo)+solve(a-2,b-2,memo)+solve(a-1,b-3,memo)); return memo[a][b]; }};

参考文献

​​808-Soup Servings​​​​[LeetCode] Soup Servings 供应汤​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。