808. 分汤 : 挺有意思的 DP 题

Myth丶恋晨 2023-10-03 21:40 8阅读 0赞

![format_png][]

### 题目描述 ###

这是 LeetCode 上的 **[808. 分汤][808.]** ，难度为 **中等**。

Tag : 「数学」、「动态规划」、「线性 DP」

有 `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\}10−5 的范围内将被认为是正确的。

示例 1:

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

示例 2:

输入: n = 100
    
    输出: 0.71875
    复制代码

提示:

*  0 <= n <= 10^90<=n<=109

### 数学 + 动态规划 ###

四种分配方式都是 2525 的倍数，因此我们可以将 nn 进行除以 2525 上取整的缩放操作，并将四类操作等价成：

1.  提供 `4ml` 的 汤A 和 `0ml` 的 汤B 。
2.  提供 `3ml` 的 汤A 和 `1ml` 的 汤B 。
3.  提供 `2ml` 的 汤A 和 `2ml` 的 汤B 。
4.  提供 `1ml` 的 汤A 和 `3ml` 的 汤B 。

定义 f\[i\]\[j\]f\[i\]\[j\] 为 汤A 剩余 ii 毫升，汤B 剩余 jj 毫升时的最终概率（概率 = 汤A先分配完的概率 + 汤A和汤B同时分配完的概率 \\times 0.5概率=汤A先分配完的概率+汤A和汤B同时分配完的概率×0.5）。

最终答案为 f\[n\]\[n\]f\[n\]\[n\] 为最终答案，考虑任意项存在为 00 情况时的边界情况：

*  若 i = 0i=0 且 j = 0j=0，结果为 0 + \\frac\{1\}\{2\} = \\frac\{1\}\{2\}0+21=21，即有 f\[0\]\[0\] = 0.5f\[0\]\[0\]=0.5
 *  若 i = 0i=0 且 j > 0j>0，结果为 1 + 0 = 11+0=1，即有 f\[0\]\[X\] = 1f\[0\]\[X\]=1，其中 X > 1X>1
 *  若 i > 0i>0 且 j = 0j=0，结果为 0 + 0 = 00+0=0，即有 f\[X\]\[0\] = 0f\[X\]\[0\]=0，其中 X > 1X>1

其余一般情况为 ii 和 jj 均不为 00，由于四类操作均为等概率，结合题意和状态定义可知：

f\[i\]\[j\] = \\frac\{1\}\{4\} \\times (f\[i - 4\]\[j\] + f\[i - 3\]\[j - 1\] + f\[i - 2\]\[j - 2\] + f\[i - 1\]\[j - 3\])f\[i\]\[j\]=41×(f\[i−4\]\[j\]+f\[i−3\]\[j−1\]+f\[i−2\]\[j−2\]+f\[i−1\]\[j−3\])

由于 n = 1e9n=1e9，即使进行了除 2525 的缩放操作，过多的状态数仍会导致 `TLE`。

此时需要利用「返回值在正确答案 10^\{-5\}10−5 的范围内将被认为是正确的」来做优化（一下子不太好想到）：由于四类操作均是等概率，单个回合期望消耗汤 A 的量为 2.52.5，消耗汤 B 的量为 1.51.5。

因此当 nn 足够大，操作回合足够多，汤 A 将有较大的概率结束分配，即当 nn 足够大，概率值会趋向于 11。

我们考虑多大的 nn 能够配合精度误差 10^\{-5\}10−5 来减少计算量：一个可行的操作是利用上述的 DP 思路 + 二分的方式找到符合精度要求的验算值（不超过 200200）。

Java 代码：

class Solution {
        public double soupServings(int n) {
            n = Math.min(200, (int) Math.ceil(n / 25.0));
            double[][] f = new double[n + 10][n + 10];
            f[0][0] = 0.5;
            for (int j = 1; j <= n; j++) f[0][j] = 1;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    double a = f[Math.max(i - 4, 0)][j], b = f[Math.max(i - 3, 0)][Math.max(j - 1, 0)];
                    double c = f[Math.max(i - 2, 0)][Math.max(j - 2, 0)], d = f[Math.max(i - 1, 0)][Math.max(j - 3, 0)];
                    f[i][j] = 0.25 * (a + b + c + d);
                }
            }
            return f[n][n];
        }
    }
    复制代码

Python 代码：

class Solution:
        def soupServings(self, n: int) -> float:
            n = min(200, math.ceil(n / 25))
            f = [[0] * (n + 10) for _ in range(n + 10)]
            f[0][0] = 0.5
            for j in range(1, n + 10):
                f[0][j] = 1
            for i in range(1, n + 1):
                for j in range(1, n + 1):
                    a, b = f[max(i - 4, 0)][j], f[max(i - 3, 0)][max(j - 1, 0)]
                    c, d = f[max(i - 2, 0)][max(j - 2, 0)], f[max(i - 1, 0)][max(j - 3, 0)]
                    f[i][j] = 0.25 * (a + b + c + d)
            return f[n][n]
    复制代码

*  时间复杂度：O(m^2)O(m2)，其中 m = 200m=200 为验算值
 *  空间复杂度：O(m^2)O(m2)

### 最后 ###

这是我们「刷穿 LeetCode」系列文章的第 `No.808` 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：[github.com/SharingSour…][github.com_SharingSour] 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

[format_png]: https://img-blog.csdnimg.cn/img_convert/ec3eadeaabcd7ccd2e63c333297b6bee.webp?x-oss-process=image/format,png
[808.]: https://link.juejin.cn/?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fsoup-servings%2Fsolution%2Fby-ac_oier-3n1h%2F
[github.com_SharingSour]: https://link.juejin.cn/?target=https%3A%2F%2Fgithub.com%2FSharingSource%2FLogicStack-LeetCode