同事接了个紧急项目，加班到凌晨完成，却被当众批效率低。。

今天我们聊点有趣的算法题：分汤问题。

分汤这个问题看着像是在吃饭的时候琢磨的吧？咱就说，算法的浪漫也太接地气了。不过别小看它，虽然名字朴实无华，但背后可是满满的动态规划（Dynamic Programming）精髓。

问题描述

假设有两锅汤 A 和 B，每次你只能选择某种固定方式来盛汤，比如：

1. 从 A 锅取 100 毫升，从 B 锅取 0 毫升。
2. 从 A 锅取 75 毫升，从 B 锅取 25 毫升。
3. 从 A 锅取 50 毫升，从 B 锅取 50 毫升。
4. 从 A 锅取 25 毫升，从 B 锅取 75 毫升。

目标是把 A 和 B 都分完，但可能在某个时刻一锅已经分完了。题目让你算：A 先分完的概率是多少？

听着是不是有点绕？其实总结下来就是：动态规划模拟这四种操作，统计概率就行。

动态规划解法

动态规划的核心在于，把问题分解成可以重复利用的子问题，用状态转移来逐步求解。这里的状态是什么？两个变量：

• (dp[i][j])：表示 A 剩余 (i) 毫升，B 剩余 (j) 毫升时，A 先分完的概率。

状态转移方程

如果 (i \leq 0) 且 (j > 0)，说明 A 分完了但 B 还有剩，概率为 1。如果 (j \leq 0) 且 (i > 0)，说明 B 分完了但 A 还有剩，概率为 0。如果 (i \leq 0) 且 (j \leq 0)，两锅同时分完，按题意概率为 0.5。

否则，剩余的概率通过这四种操作取平均值：

[ dp[i][j] = 0.25 \cdot (dp[i-100][j] + dp[i-75][j-25] + dp[i-50][j-50] + dp[i-25][j-75]) ]

代码实现来了，安排上👇：

public double soupServings(int n) {
    if (n > 4800) return 1.0; // 优化处理，大量计算下结果趋近于 1
    n = (int) Math.ceil(n / 25.0);
    double[][] dp = new double[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 && j == 0) {
                dp[i][j] = 0.5; // A 和 B 同时分完
            } else if (i == 0) {
                dp[i][j] = 1.0; // A 分完，B 还剩
            } else if (j == 0) {
                dp[i][j] = 0.0; // B 分完，A 还剩
            } else {
                dp[i][j] = 0.25 * (
                    getProbability(dp, i - 4, j) +
                    getProbability(dp, i - 3, j - 1) +
                    getProbability(dp, i - 2, j - 2) +
                    getProbability(dp, i - 1, j - 3)
                );
            }
        }
    }
    return dp[n][n];
}
private double getProbability(double[][] dp, int i, int j) {
    if (i < 0 && j < 0) return 0.5; // 两锅同时分完
    if (i < 0) return 1.0;         // A 分完
    if (j < 0) return 0.0;         // B 分完
    return dp[i][j];
}

优化小技巧

当 (n) 很大时，比如超过 4800，计算结果已经趋近于 1。原因是 A 锅在每轮分汤中被取空的概率占主导，所以直接返回 1.0 省点力气。这个小优化既提高效率，又能避免内存炸裂，完美！