LeetCode - 808. Soup Servings

Medium

808. Soup Servings

Problem

There are two types of soup: type A and type B, each starting with n ml. On every turn, one of the following four operations is chosen at random, each with probability 0.25:

• 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

If the remaining volume of a soup is insufficient, pour all that remains. The process stops once at least one soup is depleted. Return the probability that A becomes empty before B, plus half the probability that both become empty at the same time. Answers within 10^-5 are accepted.

Example 1:

Input: n = 50
Output: 0.62500
Explanation:

• Operation 1 & 2 → A empty first
• Operation 3 → both empty same turn
• Operation 4 → B empty first
  Summing probabilities: 0.25*(1 + 1 + 0.5 + 0) = 0.625

Example 2:

Input: n = 100
Output: 0.71875

Constraints:

• 0 <= n <= 10^9

---

解題思路

1. 先把問題縮小
   因為每次倒湯的量都是 25 的倍數，所以可以直接把 n 換成 m = ceil(n / 25)，這樣狀態就從原本的 n 級別，變成 m 級別，瞬間小很多

2. 超大數直接跳過計算
   實測發現 n >= 5000 的時候，機率已經接近到 1（差距小於 10^-5），
   所以可以直接 return 1.0，根本不用跑 DP，可以省很多時間

3. 狀態定義
   設 dp[i][j] 表示 A 剩 i 單位、B 剩 j 單位時，A 先空的機率 + 同時空的一半機率

4. 邊界條件

• A ≤ 0 且 B ≤ 0 → 同時空 → 回傳 0.5
• A ≤ 0 且 B > 0 → A 先空 → 回傳 1.0
• B ≤ 0 且 A > 0 → B 先空 → 回傳 0.0

5. 轉移公式
   四種操作機率一樣，每種 0.25，所以直接平均四個下一狀態的值

6. Time & Space Complexity

• 最多狀態數是 m²，其中 m ≈ n/25。
• 但因為直接砍掉 n ≥ 5000 的情況，當 n < 5000 時 m 大約是 200，所以實際時間複雜度是 O(1) 級別，空間也是 O(1)

因為註解是邊解邊寫的，我覺得我註解寫的比較容易理解，可以直接看註解去理解這題 XD

---

Solution Code

class Solution {
public:
    double soupServings(int n) {
        if (n > 5000) return 1.0; // 因為當 n 很大時，A 總是比 B 更容易先倒完(A沒有case會不倒湯)，機率會迅速趨近 1，n ≥ 5000 時與 1 的差距已小於 10⁻⁵，所以可直接回傳 1.0

        // ceil: 無條件向上取整，記得要用浮點數；ex: 1 / 25 = 0.0 向上取整還是 0，但 1 / 25.0 = 0.04 向上取整為 1，有差
        int m = ceil(n / 25.0); // 以 25 為單位，看 n 需要多少單位才能倒完
        vector<vector<double>> dp(m+1, vector<double>(m+1, 0.0));
        dp[0][0] = 0.5; // 初始化，[0][0] 代表 A B 都是空的，平手的成績是 1 / 2 = 0.5

        // dp[i][j] 代表 A 倒了 i 個 25 單位，B 倒了 j 個 25 單位
        for(int i = 1; i <= m; ++i){ 
            dp[i][0] = 0.0; // 因為如果 [i][0] 代表 B 先空了，此時獲勝機率為 0
            dp[0][i] = 1.0; // 同理，[0][i] 代表 A 先空了，此時獲勝機率為 1
            for(int j = 1; j <= i; ++j){
                // 其實可以發現每次倒湯都是 4 個 25 單位的總和，所以這裏去找能組成現在這格水量的那四種倒湯法
                // ex: [i-4][j] 代表的是少 4*25 單位前的 dp 狀態，因為如果該狀態我倒了 100ml A、0 ml B 之後就會變成現在的 [i][j] 狀態
                // ex: dp[1][1] 代表的是 A 和 B 目前都各有 25 ml 的機率
                // 最後除以 4，因為這裡每個 dp 發生機率都是 0.25
                dp[i][j] = (dp[max(0, i-4)][max(0, j)] + dp[max(0, i-3)][max(0, j-1)] + dp[max(0, i-2)][max(0, j-2)] + dp[max(0, i-1)][max(0, j-3)]) / 4;
                dp[j][i] = (dp[max(0, j-4)][max(0, i)] + dp[max(0, j-3)][max(0, i-1)] + dp[max(0, j-2)][max(0, i-2)] + dp[max(0, j-1)][max(0, i-3)]) / 4;
            } 
        }
        return dp[m][m];
    }
};