LeetCode 799. 香槟塔

2022-03-28 HGNULB 约 10 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 799. 香槟塔

题意分析

一堆杯子摞成金字塔：第 $0$ 行 $1$ 个杯子，第 $1$ 行 $2$ 个，第 $i$ 行 $i+1$ 个。每个杯子容量都是 $1$。从最顶上那个杯子倒入 poured 杯香槟，杯子装满之后多余的部分平均分成两份，分别流向正下方左右两个杯子；最底层溢出的酒直接流到地上。所有酒瞬间流完（不考虑时间），问第 queryRow 行第 queryGlass 个杯子里最终有多少酒（返回 $0$ 到 $1$ 之间的小数）。

题面里「多余的平均流向下方两个杯子」这句话给出了明确的层间递推关系：某一行的溢出量完全决定了下一行的流入量，而下一行的状态又不会反过来影响上一行。这种单向、逐层的依赖，正是自顶向下逐行推进的信号，也说明用一个二维表按行填充就能算清楚。

第二个信号是「问的是某一个具体位置」而不是整座塔。queryRow 的上限是 $99$，也就是最多只需要模拟 $100$ 行，共约 $5000$ 个杯子——规模极小，完全不需要任何优化，但也提醒我们没必要模拟到 $99$ 行以外。

第三个信号是「杯子容量为 $1$，超出部分才往下流」。这意味着表里存的量和杯子里实际的量不是一回事：一个杯子可能被倒进 $5$ 单位的酒，但它只能留住 $1$，剩下 $4$ 才是溢出。把这两个概念混为一谈是本题最大的坑。

约束方面：poured 最大是 $10^9$，queryRow 和 queryGlass 都在 $0$ 到 $99$ 之间，且保证 queryGlass <= queryRow。$10^9$ 这个量级说明必须用浮点数而不是整数——溢出量会被反复除以 $2$ 产生分数；同时也说明顶部的数值很大，但由于每层平摊，几层之后就会迅速衰减。

边界上要覆盖：poured = 0（答案是 $0$）；poured = 1（只有顶杯是满的，其余全为 $0$）；queryRow = 0（直接问顶杯，答案是 $\min(1, poured)$）；查询的是某一行最边上的杯子（它只接收来自上一行同侧唯一一个杯子的分流）；poured 极大使得目标杯子被灌满。

解法：动态规划模拟

核心思路

先想能不能用公式。从顶点到某个杯子的路径数是组合数 $\binom{r}{c}$，看起来像杨辉三角，很容易误以为答案是 $poured \cdot \binom{r}{c} / 2^r$。但这个式子只在没有任何杯子被灌满的假想情况下成立——真实规则里每个杯子会先扣下 $1$ 单位再往下分，这个「截留」是非线性的，破坏了叠加性，所以闭式公式不存在，必须逐层模拟。

暴力的模拟是「一杯一杯地倒」：倒 $10^9$ 次，每次追踪一滴酒的流向。这显然不可行。瓶颈在于把 poured 当成了离散的次数，而实际上酒是可以整体处理的连续量——一次性把 poured 全部倒进顶杯，再让溢出逐层传播即可。

关键观察是：只要把「流入某个杯子的总量」作为状态，层与层之间就构成了一个干净的递推。设 dp[r][c] 表示流经第 r 行第 c 个杯子的酒的总量（注意是流经量，不是留存量，可以大于 $1$）。那么这个杯子的溢出量是 $\max(0, dp[r][c] - 1)$，它平均流向下一行的两个位置：

dp[r+1][c] += overflow / 2

dp[r+1][c+1] += overflow / 2

下标为什么是 c 和 c+1？因为第 r 行第 c 个杯子在金字塔中的物理位置，正好压在第 r+1 行第 c 与第 c+1 两个杯子的接缝上。反过来说，第 r+1 行第 c 个杯子会同时接收来自上一行第 c-1 和第 c 两个杯子的分流——这与杨辉三角的相邻求和结构完全一致，只是求和的对象换成了溢出量。

于是维护的不变量是：按行从上到下推进，当处理第 r 行时，dp[r][*] 已经累计了所有来自第 r-1 行的分流，因此它就是该行各杯子的最终流经量。这条不变量成立的前提是外层循环必须按行递增，且在处理第 r 行之前不再往里加东西——由于所有流入只来自上一行，这一点自然满足。

最后一步是把「流经量」翻译回「杯中留存量」：答案是 $\min(1, dp[queryRow][queryGlass])$。杯子最多装 $1$，多的都流走了，所以必须做这个截断。

两个实现细节值得点明。其一，只需要模拟到第 queryRow 行为止，再往下的行对答案没有影响，所以外层循环写 r <= queryRow；数组开 queryRow + 2 行是为了让第 queryRow 行的溢出有地方写（虽然那一行的写入不会被读取，但不开会越界）。其二，overflow > 0 的判断不只是优化：不加的话会给下一行加上负数，直接把结果算错。

解题步骤

开一个 (queryRow + 2) × (queryRow + 2) 的二维 double 数组 dp。理由：行数要比 queryRow 多两行，因为循环推进到第 queryRow 行时仍会往第 queryRow + 1 行写；列数取同样大小是因为第 r 行最多有 r + 1 个杯子，且会写到下标 c + 1，用方阵最省心也不会越界。

令 dp[0][0] = poured。理由：所有酒都从顶杯倒入，这是唯一的初始状态；注意这里存的是「流经量」，可以远大于 $1$，不要在这一步就截断成 $1$，否则后面的溢出全部丢失。

外层 for (int r = 0; r <= queryRow; r++)，内层 for (int c = 0; c <= r; c++)。理由：按行递增保证了转移来源（上一行）已经全部累加完毕；内层只到 c <= r，因为第 r 行只有 r + 1 个杯子，越界的位置恒为 $0$，遍历它们纯属浪费。

每个杯子先算 overflow = Math.max(0.0, dp[r][c] - 1.0)。理由：这一步把「流经量」转成「溢出量」，是整个模拟的核心；用 max 与 $0$ 取大，是因为流经量不足 $1$ 时杯子没满，不会有任何酒往下流。

若 overflow > 0，则把 overflow / 2.0 同时累加到 dp[r+1][c] 和 dp[r+1][c+1]。理由：题目规定溢出部分平均分给下方两杯；用 += 而不是 =，因为下一行的每个杯子会收到来自上一行两个不同杯子的分流，必须累加。

循环结束后返回 Math.min(1.0, dp[queryRow][queryGlass])。理由：dp 存的是流经量，而题目问的是杯中留存量，最多为 $1$；不截断的话，被灌满的杯子会返回一个大于 $1$ 的数。

以 poured = 4、queryRow = 2、queryGlass = 1 走一遍。初始 dp[0][0] = 4。第 $0$ 行：overflow = 4 - 1 = 3，每侧分 $1.5$，于是 dp[1][0] = 1.5、dp[1][1] = 1.5。第 $1$ 行第 $0$ 杯：overflow = 1.5 - 1 = 0.5，每侧 $0.25$，dp[2][0] += 0.25、dp[2][1] += 0.25。第 $1$ 行第 $1$ 杯：overflow = 0.5，每侧 $0.25$，dp[2][1] += 0.25（累计到 $0.5$）、dp[2][2] += 0.25。第 $2$ 行（即 queryRow）也会被外层循环处理，但它的溢出写到第 $3$ 行不影响答案。最终 dp[2][1] = 0.5，截断后仍是 $0.5$，与期望一致——注意中间那个杯子收到了左右两侧各 $0.25$ 的分流，正是 += 的必要性所在；而两侧的杯子各只有 $0.25$，因为它们只被灌了一次。

代码实现

class Solution {
    public double champagneTower(int poured, int queryRow, int queryGlass) {
        double[][] dp = new double[queryRow + 2][queryRow + 2];
        dp[0][0] = poured;

        for (int r = 0; r <= queryRow; r++) {
            for (int c = 0; c <= r; c++) {
                double overflow = Math.max(0.0, dp[r][c] - 1.0);
                if (overflow > 0) {
                    dp[r + 1][c] += overflow / 2.0;
                    dp[r + 1][c + 1] += overflow / 2.0;
                }
            }
        }

        return Math.min(1.0, dp[queryRow][queryGlass]);
    }
}

func champagneTower(poured int, queryRow int, queryGlass int) float64 {
    dp := make([][]float64, queryRow+2)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]float64, queryRow+2)
    }
    dp[0][0] = float64(poured)

    for r := 0; r <= queryRow; r++ {
        for c := 0; c <= r; c++ {
            overflow := dp[r][c] - 1.0
            if overflow > 0 {
                share := overflow / 2.0
                dp[r+1][c] += share
                dp[r+1][c+1] += share
            }
        }
    }

    if dp[queryRow][queryGlass] > 1.0 {
        return 1.0
    }
    return dp[queryRow][queryGlass]
}

复杂度分析

时间复杂度：$O(r^2)$，其中 $r$ 是 queryRow。外层遍历 $r + 1$ 行，第 $i$ 行内层遍历 $i + 1$ 个杯子，总杯子数是 $\frac{(r+1)(r+2)}{2}$，每个杯子只做一次减法、一次比较和两次累加。$r \le 99$ 时约 $5000$ 次操作，可以忽略不计。

空间复杂度：$O(r^2)$，二维数组开了 $(r+2)^2$ 个 double。由于每一行只依赖上一行，可以改成两个长度为 $r+2$ 的一维数组滚动，把空间降到 $O(r)$；本题 $r \le 99$，二维表只占几十 KB，为了代码直观保留二维是合理取舍。

关键点总结

状态定义要先分清「流经量」和「留存量」。本题 dp 存的是前者（可以远大于 $1$），只有在返回时才用 $\min(1, \cdot)$ 转成后者。把这两个概念混在一个数组里，会导致溢出量被提前截断，整座塔的传播全错——这是本题最核心的设计决策。

「上层单向影响下层」的模拟题，用按行递推就能保证转移来源已就绪，不需要任何拓扑排序或记忆化。判断依据是「依赖是否只指向前一层」，一旦是，循环顺序自然确定。

一个位置被多个来源累加时必须用 += 而不是 =。本题第 r+1 行第 c 杯同时接收上一行第 c-1 和第 c 的分流，与杨辉三角的相邻求和是同一个结构，这个结构在网格路径计数、概率传播里反复出现。

只算到需要的那一层就停。queryRow 之下的行对答案没有任何影响，模拟到 $99$ 行以外纯属浪费；同理内层只需遍历 c <= r，因为超出的位置恒为 $0$。

涉及反复二分的量必须用浮点数。本题 poured 是整数但溢出会被不断除以 $2$，用 int 会在第一次分流时就截断成 $0$；同时因为总量有界且层数不多，double 的精度误差远小于判题允许的 $10^{-5}$。

面试视角：字节和小米考这题看的是能否把物理过程正确翻译成状态转移。答题时最容易被追问的两点是「为什么 dp 里存的可以大于 1」和「为什么要用 min 截断」，提前主动讲清这两者的区别基本就稳了。若被追问优化，直接答「每行只依赖上一行，可以用两个一维数组滚动，空间从 $O(r^2)$ 降到 $O(r)$」；若被追问「能不能用组合数公式」，要能指出「杯子截留 $1$ 单位破坏了线性叠加，所以公式不成立」。

易错点总结

错误写法：初始化写成 dp[0][0] = Math.min(1.0, poured) → 用例 poured = 4，queryRow = 2，queryGlass = 1 → 顶杯的流经量被提前截成 $1$，溢出量变成 $0$，下面所有杯子都是 $0$，返回 $0$，正确答案是 $0.5$。

错误写法：返回时忘记 Math.min(1.0, ...) → 用例 poured = 100000009，queryRow = 33，queryGlass = 17 → 目标杯子的流经量远大于 $1$，直接返回该值，而杯子最多只能装 $1$。

错误写法：分流时用 = 而不是 += → 用例 poured = 4，queryRow = 2，queryGlass = 1 → 中间杯子只收到来自右上方的 $0.25$，左上方的贡献被覆盖，返回 $0.25$，正确答案是 $0.5$。

错误写法：不判 overflow > 0 就直接把 (dp[r][c] - 1) / 2 加到下一行 → 用例 poured = 1，queryRow = 1，queryGlass = 0 → 顶杯流经量恰为 $1$，overflow = 0 尚可；但 poured = 0 时 overflow = -1，下一行被加上 $-0.5$，返回负数，正确答案是 $0$。

错误写法：分流下标写成 dp[r+1][c-1] 和 dp[r+1][c] → 用例 poured = 2，queryRow = 1，queryGlass = 0 → c = 0 时下标 $-1$ 越界；即便钳到 $0$，酒的流向也整体左偏，塔不再对称。

错误写法：用 int 或 long 存 dp → 用例 poured = 2，queryRow = 1，queryGlass = 0 → 溢出量 $1$ 除以 $2$ 整除成 $0$，第一行两个杯子都是 $0$，返回 $0$，正确答案是 $0.5$。

错误写法：数组只开 queryRow + 1 行 → 用例 queryRow = 0，poured = 2 → 处理第 $0$ 行时要写 dp[1][0]，数组越界抛异常。

错误写法：内层循环写成 c <= queryRow 而不是 c <= r → 用例任意输入 → 会遍历到第 r 行本不存在的杯子，虽然它们的值都是 $0$、overflow 为负而被 max 挡住，但一旦漏写 overflow > 0 的判断，这些幽灵杯子会往下一行注入负数。

错误写法：用组合数公式 poured * C(r, c) / 2^r 直接算 → 用例 poured = 4，queryRow = 2，queryGlass = 1 → 得到 $4 \times 2 / 4 = 2$，截断后是 $1$，正确答案是 $0.5$；杯子的截留使叠加性失效，公式不成立。

错误写法：外层循环写成 r < queryRow → 用例 queryRow = 0，poured = 2 → 循环一次都不执行，dp[0][0] 虽已初始化能侥幸返回 $1$，但把查询改成 queryRow = 1 时第 $0$ 行的溢出从未被分流，返回 $0$，正确答案是 $0.5$。

相似题目

题目	难度	考察点
118. 杨辉三角	简单	完全相同的三角形累加结构，但没有「容量截留」这层非线性
120. 三角形最小路径和	中等	同样是逐行递推的三角形 DP，但状态取最小值而非累加，且可自底向上
931. 下降路径最小和	中等	层间转移涉及三个来源，练习「多来源合并」时下标范围的边界处理
64. 最小路径和	中等	网格上的单向递推，用来对照理解「依赖方向决定循环顺序」这条通则
119. 杨辉三角 II	简单	只要某一行的结果，正好练习把二维表压成一维滚动数组的写法