题目形容
这是 LeetCode 上的 808. 分汤 ，难度为 中等。
Tag : 「数学」、「动静布局」、「线性 DP」
有 A 和 B 两种类型 的汤。一开始每种类型的汤有 n 毫升。有四种调配操作：
- 提供
100ml的 汤A 和0ml的 汤B 。 - 提供
75ml的 汤A 和25ml的 汤B 。 - 提供
50ml的 汤A 和50ml的 汤B 。 - 提供
25ml的 汤A 和75ml的 汤B 。
当咱们把汤调配给某人之后，汤就没有了。每个回合，咱们将从四种概率同为 0.25 的操作中进行调配抉择。如果汤的残余量不足以实现某次操作，咱们将尽可能调配。当两种类型的汤都调配完时，进行操作。
留神 不存在先调配 100 ml 汤B 的操作。
须要返回的值： 汤A 先调配完的概率 + 汤A和汤B 同时调配完的概率 / 2。返回值在正确答案 $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^9$
数学 + 动静布局
四种调配形式都是 $25$ 的倍数，因而咱们能够将 $n$ 进行除以 $25$ 上取整的缩放操作，并将四类操作等价成：
- 提供
4ml的 汤A 和0ml的 汤B 。 - 提供
3ml的 汤A 和1ml的 汤B 。 - 提供
2ml的 汤A 和2ml的 汤B 。 - 提供
1ml的 汤A 和3ml的 汤B 。
定义 $f[i][j]$ 为 汤A 残余 $i$ 毫升，汤B 残余 $j$ 毫升时的最终概率（$概率 = 汤A先调配完的概率 + 汤A和汤B同时调配完的概率 \times 0.5$）。
最终答案为 $f[n][n]$ 为最终答案，思考任意项存在为 $0$ 状况时的边界状况：
- 若 $i = 0$ 且 $j = 0$，后果为 $0 + \frac{1}{2} = \frac{1}{2}$，即有 $f[0][0] = 0.5$
- 若 $i = 0$ 且 $j > 0$，后果为 $1 + 0 = 1$，即有 $f[0][X] = 1$，其中 $X > 1$
- 若 $i > 0$ 且 $j = 0$，后果为 $0 + 0 = 0$，即有 $f[X][0] = 0$，其中 $X > 1$
其余个别状况为 $i$ 和 $j$ 均不为 $0$，因为四类操作均为等概率，联合题意和状态定义可知：
$$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])$$
因为 $n = 1e9$，即便进行了除 $25$ 的缩放操作，过多的状态数仍会导致 TLE。
此时须要利用「返回值在正确答案 $10^{-5}$ 的范畴内将被认为是正确的」来做优化（一下子不太好想到）：因为四类操作均是等概率，单个回合冀望耗费汤 A 的量为 $2.5$，耗费汤 B 的量为 $1.5$。
因而当 $n$ 足够大，操作回合足够多，汤 A 将有较大的概率完结调配，即当 $n$ 足够大，概率值会趋向于 $1$。
咱们思考多大的 $n$ 可能配合精度误差 $10^{-5}$ 来缩小计算量：一个可行的操作是利用上述的 DP 思路 + 二分的形式找到合乎精度要求的验算值（不超过 $200$）。
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)$，其中 $m = 200$ 为验算值
- 空间复杂度：$O(m^2)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.808 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布