Keshawn_lu's Blog

Leetcode 808. 分汤

动态规划
字数统计: 631阅读时长: 2 min
2022/11/21 Share

题目简介：

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

  1. 提供 100ml 的 汤A 和 0ml 的 汤B 。
  2. 提供 75ml 的 汤A 和 25ml 的 汤B 。
  3. 提供 50ml 的 汤A 和 50ml 的 汤B 。
  4. 提供 25ml 的 汤A 和 75ml 的 汤B 。

当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为 0.25 的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。

注意 不存在先分配 100 ml 汤B 的操作。

需要返回的值： 汤A 先分配完的概率 + 汤A和汤B 同时分配完的概率 / 2。返回值在正确答案 10^-5 的范围内将被认为是正确的。

示例 1:

1
2
3
4
5
6
输入: n = 50
输出: 0.62500
解释:如果我们选择前两个操作，A 首先将变为空。
对于第三个操作，A 和 B 会同时变为空。
对于第四个操作，B 首先将变为空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。

提示:

  • 0 <= n <= 10^9

思路：

由于每次操作都是25ml的倍数，因此我们先将n / 25，将25ml汤视为1份。

动态规划，dp[i][j]代表剩余i份A和j份B时的结果概率。

当i <= 0, j <= 0时，两种汤都分配完了，返回0.5。

当i <= 0, j > 0时，A汤都分配完了，返回1.0。

当i <= 0, j >= 0时，B汤都分配完了，返回0.0。

由于我们有四种操作方式，并且概率相等，因此dp[a][b] = 0.25 * (dfs(a - 4, b) + dfs(a - 3, b - 1) + dfs(a - 2, b - 2) + dfs(a - 1, b - 3))。

tip:

  • 由于精度原因，因此当n > 4800时直接返回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
28
29
30
31
32
class Solution {
public:
    double soupServings(int n) {

        int num = ceil(double(n) / 25);

        if(n > 4800)
            return 1.0;

        vector<vector<double>> dp(num + 1, vector<double>(num + 1, 0.0));

        function<double(int, int)> dfs = [&](int a, int b){

            if(a <= 0 && b <= 0)
                return 0.5;
            if(a <= 0)
                return 1.0;
            if(b <= 0)
                return 0.0;

            if(dp[a][b] > 0)
                return dp[a][b];

            dp[a][b] = 0.25 * (dfs(a - 4, b) + dfs(a - 3, b - 1) + 
                            dfs(a - 2, b - 2) + dfs(a - 1, b - 3));

            return dp[a][b];
        };

        return dfs(num, num);
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网