题目

你有两种汤，A 和 B，每种初始为 n 毫升。在每一轮中，会随机选择以下四种操作中的一种，每种操作的概率为 0.25，且与之前的所有轮次无关：

从汤 A 取 100 毫升，从汤 B 取 0 毫升
从汤 A 取 75 毫升，从汤 B 取 25 毫升
从汤 A 取 50 毫升，从汤 B 取 50 毫升
从汤 A 取 25 毫升，从汤 B 取 75 毫升

注意：

不存在从汤 A 取 0 ml 和从汤 B 取 100 ml 的操作。
汤 A 和 B 在每次操作中同时被取出。
如果一次操作要求你取出比剩余的汤更多的量，请取出该汤剩余的所有部分。

操作过程在任何回合中任一汤被取完后立即停止。

返回汤 A 在 B 前取完的概率，加上两种汤在 同一回合 取完概率的一半。返回值在正确答案 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 解释： 如果我们选择第一个操作，A 首先将变为空。如果我们选择第二个操作，A 将在执行操作 [1, 2, 3] 时变为空，然后 A 和 B 在执行操作 4 时同时变空。如果我们选择第三个操作，A 将在执行操作 [1, 2] 时变为空，然后 A 和 B 在执行操作 3 时同时变空。如果我们选择第四个操作，A 将在执行操作 1 时变为空，然后 A 和 B 在执行操作 2 时同时变空。所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.71875。

提示:

0 <= n <= 10^9

解题思路

1. 离散化与状态定义

由于每次操作的取汤量都是25毫升的倍数，我们可以将问题简化。

将初始汤量 n 转换为 N = ceil(n / 25)。
将四种操作的取汤量也相应地除以25：
- (A, B) = (4, 0)
- (A, B) = (3, 1)
- (A, B) = (2, 2)
- (A, B) = (1, 3)

现在，我们的问题可以重新表述为：在初始量都为 N 的情况下，每次从 A 和 B 中取走上述四种组合中的一种，求满足条件的概率。

2. 特殊情况处理

当 n 很大时，汤 A 和 B 几乎是同时被取完的。这是因为每次操作都倾向于从 A 取走更多的汤，但汤 B 也在被消耗。当 n 趋于无穷大时，两种汤同时取完的概率会越来越接近。经过分析，当 n 足够大（例如 n >= 5000 或 N >= 200），所求概率会非常接近一个定值。为了避免在 n 很大时进行复杂的计算，我们可以直接返回一个近似值 1.0。这是一个常见的技巧，因为操作 (100, 0) 会使得 A 消耗得更快，随着轮次增加，A 先取完的概率会越来越高。当 n 很大时，这个概率会非常接近1。

3. 动态规划或记忆化搜索

我们可以用动态规划或记忆化搜索来解决这个问题。

状态：我们可以用 dp[i][j] 来表示汤 A 剩余 i * 25 毫升、汤 B 剩余 j * 25 毫升时，达到目标（A 先取完，或 A、B 同时取完）的概率。
状态转移：
- dp[i][j] 可以通过四种操作从四个不同的状态转移而来。
- dp[i][j] = 0.25 * (dp[i+4][j] + dp[i+3][j+1] + dp[i+2][j+2] + dp[i+1][j+3])
- 这里我们用 i 和 j 代表剩余汤的量，所以转移方程看起来是“加”，但实际上是在“减”。如果我们用 i 和 j 表示已经取出的汤的量，状态转移会更直观。
记忆化搜索 (DFS with Memoization)：这是一个更直接的思路。我们可以定义一个函数 dfs(a, b)，表示当汤 A 和 B 分别还剩 a 和 b 份（每份25毫升）时的概率。
- 函数定义: dfs(a, b) 返回一个包含两个元素的数组 [p1, p2]，其中 p1 是汤 A 在汤 B 前取完的概率，p2 是汤 A 和汤 B 同时取完的概率。
- 递归基 (Base Cases):
  - 如果 a <= 0 且 b <= 0：两汤同时取完。返回 [0, 1]。
  - 如果 a <= 0：汤 A 先取完。返回 [1, 0]。
  - 如果 b <= 0：汤 B 先取完。返回 [0, 0]。（因为我们只关心 A 先取完的情况，B 先取完对结果贡献为0）。
- 递归步骤:
  - dfs(a, b) = 0.25 * (dfs(a-4, b) + dfs(a-3, b-1) + dfs(a-2, b-2) + dfs(a-1, b-3))
  - 注意：在每次递归调用中，我们要处理“取出的量比剩余的汤多”的情况。例如 a-4 应该是 max(0, a-4)。
  - 最终，我们将四个子问题的结果数组相加，再乘以 0.25，得到 dfs(a, b) 的结果。

4. 优化与注意事项

浮点数精度: 由于涉及概率计算，需要使用 double 或 float 类型来存储和计算。
边界条件: 需要处理好 n <= 0 的情况。如果 n=0，两汤同时取完，概率为1，所以所求值为 1/2。
结果计算:
- result = 0.25 * (dfs(n-100, n) + ...)
- 最终结果是 A先取完的概率 + (A和B同时取完的概率)/2。我们可以直接在 dfs 函数中将这两个概率分开计算，最后再相加。
- 另一种方法是 dfs 返回一个概率值，表示“A先取完的概率 + 0.5 * A和B同时取完的概率”。
- 比如 dfs(a, b) 直接返回所求值，递归基变为：
  - a <= 0 且 b <= 0: 返回 0.5
  - a <= 0: 返回 1.0
  - b <= 0: 返回 0.0
  - 否则，递归求和。这种方法更简洁。

具体代码

class Solution {
public:
    // memo 是一个二维向量，用于存储已经计算过的状态的概率。
    // memo[i][j] 存储汤 A 剩余 i 份、汤 B 剩余 j 份时的概率。
    // 使用 0.0 作为初始值，当计算出某个状态的概率后，会将其存入 memo 中，
    // 这样下次遇到相同的状态时就可以直接返回，避免重复计算。
    vector<vector<double>> memo;

    /**
     * @brief 使用记忆化搜索计算在给定汤量下满足条件的概率。
     * @param a 汤 A 剩余的份数（每份 25ml）。
     * @param b 汤 B 剩余的份数（每份 25ml）。
     * @return 汤 A 先取完的概率，加上两汤同时取完概率的一半。
     */
    double dfs(int a, int b) {
        // 递归基（Base Cases）：
        // 当 A 和 B 的汤都用完时，认为它们同时取完。根据题意，这部分概率计入 0.5。
        if (a <= 0 && b <= 0) {
            return 0.5;
        }
        // 当 A 的汤用完，但 B 的汤还有剩余时，A 先取完。这部分概率计入 1.0。
        if (a <= 0) {
            return 1.0;
        }
        // 当 B 的汤用完，但 A 的汤还有剩余时，B 先取完。根据题意，这部分对结果贡献为 0。
        if (b <= 0) {
            return 0.0;
        }
        
        // 如果当前状态 (a, b) 已经计算过，直接返回存储的结果，避免重复计算。
        // memo[a][b] > 0 是因为概率值不会是负数，而 0.0 可能是未计算或最终结果就是 0.0。
        // 由于所有概率都是非负的，且我们处理了 b <= 0 的情况，所以 0.0 只在 b 剩余多于 a 时出现，
        // 而在这种情况下 A 不可能先取完。所以这里用 > 0 的判断是可行的。
        if (memo[a][b] > 0) {
            return memo[a][b];
        }

        // 递归转移：
        // 每次有 0.25 的概率选择四种操作中的一种。
        // 1. 从 A 取 100ml (4份), B 取 0ml (0份)
        // 2. 从 A 取 75ml (3份), B 取 25ml (1份)
        // 3. 从 A 取 50ml (2份), B 取 50ml (2份)
        // 4. 从 A 取 25ml (1份), B 取 75ml (3份)
        // 在计算新的汤量时，使用 max(0, ...) 来确保汤的量不会变成负数，
        // 对应“如果一次操作要求你取出比剩余的汤更多的量，请取出该汤剩余的所有部分”的规则。
        double prob = 0.25 * (dfs(max(0, a - 4), b) +
                              dfs(max(0, a - 3), max(0, b - 1)) +
                              dfs(max(0, a - 2), max(0, b - 2)) +
                              dfs(max(0, a - 1), max(0, b - 3)));

        // 将计算出的概率存入 memo 中，并返回。
        return memo[a][b] = prob;
    }

    /**
     * @brief 主函数，计算汤的概率。
     * @param n 汤的初始量，单位毫升。
     * @return 满足条件的概率。
     */
    double soupServings(int n) {
        // 特殊情况处理：
        // 当 n 足够大时，汤 A 先取完的概率趋近于 1。
        // 经验表明，当 n >= 5000 时，结果与 1.0 的误差已经非常小，可以满足题目的精度要求。
        if (n >= 5000) {
            return 1.0;
        }
        
        // 离散化处理：
        // 将汤的初始量 n 转换为 25ml 为一份的份数。
        // 使用 (n + 24) / 25 是一种常见的向上取整技巧，等同于 ceil(n / 25.0)。
        int m = (n + 24) / 25;
        
        // 初始化记忆化数组，大小为 (m+1) x (m+1)，所有值都为 0.0。
        // m+1 是因为份数可能从 0 到 m。
        memo.assign(m + 1, vector<double>(m + 1, 0.0));
        
        // 从初始状态 (m, m) 开始递归计算。
        return dfs(m, m);
    }
};

808. 分汤

beautifulremi

题目