LeetCode808 分汤

发表于 | 分类于 |
字数统计: 518 | 阅读时长 ≈ 2

链接: https://leetcode.cn/problems/soup-servings/

题意

有 A 和 B 两种类型 的汤。一开始每种类型的汤有 n 毫升。有四种分配操作：

  • 提供 100ml 的 汤A 和 0ml 的 汤B 。
  • 提供 75ml 的 汤A 和 25ml 的 汤B 。
  • 提供 50ml 的 汤A 和 50ml 的 汤B 。
  • 提供 25ml 的 汤A 和 75ml 的 汤B 。
    每个回合，我们将从四种概率同为 0.25 的操作中进行分配选择。
    需要返回的值： 汤A 先分配完的概率 + 汤A和汤B 同时分配完的概率 / 2

解法

是一道概率dp的题目
dp[i][j]表示A剩余i毫升B剩余j毫升时的所求概率值
而它每次可以根据四种不同的操作转移而来
状态转移方程如下
dp[i][j] = 0.25 * (dp[i - 100][j] + dp[i - 75][j - 25] + dp[i - 50][j - 50] + dp[i - 25][j - 25])
由于每个数字都是25的倍数，所以可以将整体除以25 节省存储空间
同时对边界进行初始化
由题意可得dp[0][0] = 0.5 (两者同时被分配完的概率 / 2)
dp[0][x]都为1（汤A 先分配完的概率为1）
转移的时候还要注意可能剩余的汤量不足以减，当作整体为0的情况即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    double soupServings(int n) {
        if (n >= 4800) return 1;
        int N = (n + 24) / 25;
        vector<vector<double>> dp(N + 1, vector<double>(N + 1));
        // dp[i][j]表示A剩余i毫升B剩余j毫升时的所求概率值
        dp[0][0] = 0.5;
        for (int i = 1; i <= N; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i <= N; i++) {
            int a1 = i - 4 > 0 ? i - 4 : 0;
            int a2 = i - 3 > 0 ? i - 3 : 0;
            int a3 = i - 2 > 0 ? i - 2 : 0;
            int a4 = i - 1 > 0 ? i - 1 : 0;
            for (int j = 1; j <= N; j++) {
                int b1 = j > 0 ? j : 0;
                int b2 = j - 1 > 0 ? j - 1 : 0;
                int b3 = j - 2 > 0 ? j - 2 : 0;
                int b4 = j - 3 > 0 ? j - 3 : 0;
                dp[i][j] = 0.25 * (dp[a1][b1] + dp[a2][b2] + dp[a3][b3] + dp[a4][b4]);
            }
        }
        return dp[N][N];
    }
};