808 Soup Servings

808. Soup Servings

1. Question

There are two types of soup: type A and type B. Initially we haveNml of each type of soup. There are four kinds of operations:

1. Serve 100 ml of soup A and 0 ml of soup B

2. Serve 75 ml of soup A and 25 ml of soup B

3. Serve 50 ml of soup A and 50 ml of soup B

4. 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^-6of the true value will be accepted as correct.

2. Implementation

(1) DFS + Memoization

思路: 这题刚开始看不太好理解，但题目要求的是当soup A的量为0的概率 加上 soup A和soup B的量同时为0的概率的一半。仔细分析，我们可以得到结果可以分解为几个base case：

1.A和B的量都为0

2.A的量为0，B的量不为0

3.A的量不为0, B的量为0

根据题目要求可知，我们只需要得到base case 1和2即可, 其中我们设base case1的概率为1，base case 2的概率为0.5(因为题目要求这种情况下我们只要得到概率的一半), base case 3的概率为0， 由于选择4种操作的概率都为0.25，所以再选择每一个操作概率都要乘以0.25。通过画出递归树(比如N = 200)，我们发现会有overlapping subproblem(比如A = 25, B = 175这个subproblem出现重复)，所以需要利用记忆化搜索避免重复计算。

class Solution {
    public double soupServings(int N) {
        // 根据所给的操作我们可知，A比B早用完，通过试验计算发现当N大于5000时，概率接近1
        // 不加这个无法过OJ，但个人觉得实际面试中得到这个阈值不太现实
        if (N >= 5000) {
            return 1;
        }

        // volume for A and B for each operation
        int[][] volumes = {{100, 0}, {75, 25}, {50, 50}, {25, 75}};
        // cache[i][j]存储A量为i, B量为j时，得到结果的概率
        Double[][] cache = new Double[N + 1][N + 1];

        return getProbByDFS(N, N, cache, volumes);
    }

    public double getProbByDFS(int A, int B, Double[][] cache, int[][] volumes) {
        // Base case 2
        if (A <= 0 && B <= 0) {
            return 0.5;
        }

        // Base case 1
        if (A <= 0) {
            return 1.0;
        }

        // Base case 3
        if (B <= 0) {
            return 0;
        }

        if (cache[A][B] != null) {
            return cache[A][B];
        }

        double prob = 0;
        for (int i = 0; i < 4; i++) {
            prob += getProbByDFS(A - volumes[i][0], B - volumes[i][1], cache, volumes);
        }
        // 每个operaton选择的概率为0.25，所以这里乘上0.25
        prob *= 0.25;
        cache[A][B] = prob;
        return prob;
    }
}

3. Time & Space Complexity

DFS + Memoization:时间复杂度O(n ^ 2), 对于量为N的A和B来说，总共有N ^ 2种状态，其中通过记忆化搜索，每种状态最多只被计算一次, 空间复杂度O(n ^ 2)