LeetCode 799 香槟塔：动态规划与状态转移题解

LeetCode 799这道香槟塔，是我在刷《LeetCode 热门 100 题》之外偶然翻到的一道偏门题目。说实话第一眼看到这个题名，我还以为是道模拟倒酒的脑筋急转弯，结果越做越觉得有意思——它把几何布局、动态规划、浮点精度这几个点全部揉在了一起，代码量不大，但每一步都值得琢磨。如果你是准备面试的 Java/Python 选手，或者在刷题指南里寻找"动态规划从入门到放弃"之外的好题，这道题值得花一个下午好好啃一啃。

1. 题目到底在说什么：先读懂"倒酒模型"

1.1 题目原文与第一印象

题目设置了一个很生动的场景：我们把香槟倒在一个金字塔形状的杯架上。最顶层是第 1 行，只有 1 个杯子；第 2 行有 2 个杯子；第 3 行有 3 个杯子……依此类推，第 i 行一共有 i 个杯子。每只杯子的容量是 1 杯（姑且理解成 250ml 或者任意固定单位）。

现在从最顶层的杯子正上方缓缓倒入 poured 杯香槟。倒满之后，多余的部分会从杯子两侧溢出，均匀分给下一行紧挨着的两个杯子（左边那个和右边那个）。题目要求我们返回一个状态：当倒完指定的香槟之后，第 query_row 行、第 query_glass 个杯子里有多少香槟。

第一眼看上去，很多人会觉得这是道纯模拟题——拿个二维数组，一层一层往下算。但真上手做的时候，你会发现几个容易卡住的问题：一个杯子满了之后到底是"完全停止接收"还是"继续接收然后溢出"？溢出的量是瞬时一次性分完还是持续均分？这些细节如果不理清楚，代码写出来就是错的。

1.2 容易踩的坑：杯子满了之后去哪了

我先说最容易出错的地方。很多初学者会下意识认为，某只杯子一旦满了，后面倒入的香槟就"不关它的事"了，直接全部流到下一层。但仔细想想倒酒的实际场景：只要上面还在持续给这只杯子灌酒，这只杯子就一直处于满杯状态，多余的部分会不断地从边缘溢出去。

所以在模型里，杯子满后不是"不再接收"，而是"接收多少、就溢出多少"。也就是说，每一只杯子从上方接收到的总香槟量，先填满自己的 1 单位容量，剩余部分再分给下一层。这其实是一个典型的有损传递过程，跟水往低处流、注满一个容器之后才开始外溢的物理直觉完全一致。

除了这个核心理解，还有一个隐藏知识点：溢出的香槟是均匀分配给下一层左右两个杯子的，各拿 50%。题目里没有做任何偏心分配，所以很多人在纸上画图时，觉得"右边杯子离倒酒点更近应该多分一点"——纯粹是想多了，这就是一道数学题，不是流体力学。

1.3 为什么这个模型很适合练动态规划

当我写完第一版模拟代码，发现它的思路本质上就是动态规划一层层往下推。每一只杯子的香槟量，只依赖于它左上和右上两只杯子的溢出量，这是一个极其清晰的无后效性递推。换句话说，计算第 i 行的状态时，只需要第 i-1 行的状态，不需要更早的信息。

这类"每一步只依赖前一步"的结构，是动态规划里最容易理解、也最适合拿来练手的入门模型。更妙的是，它比常见的斐波那契、爬楼梯问题更接近真实工程里的状态流转：有容量上限、有溢出分配、有截断条件。把这道题刷透，你对"状态转移"这个词的理解会比刷十道简单 DP 都深刻。

2. 核心思路拆解：从模拟到动态规划

2.1 直接的模拟方案为什么可行

最直白的思路是：用二维数组 dp 记录每个杯子里的香槟量。先把 poured 全部放在 dp[0][0]，然后从第 0 行开始逐层往下"结算"。

每一只杯子的计算逻辑是这样的：

1. 如果 dp[i][j] 小于等于 1，说明这只杯子没满，也没有多余的香槟可以往下传递，直接跳过。
2. 如果 dp[i][j] 大于 1，说明这只杯子已经满了，它自己保留 1 单位，剩余部分 divided = (dp[i][j] - 1) / 2 分别加到下一层的 dp[i+1][j] 和 dp[i+1][j+1] 上。

由于每一行最多只有 i+1 个杯子，而查询的行号 query_row 不超过 100，所以这个二维数组最多开到 101 x 101 就足够。整体复杂度 O(query_row^2)，在这个数据范围下非常轻松。很多人担心 poured 特别大（比如 10^9）会不会超时或者溢出，实际上你只需要更新到 query_row 那一行，不需要把整个金字塔全部模拟完，所以复杂度只跟层数有关，和倒酒总量关系不大。

2.2 状态定义的由来：dp[i][j]表示什么

我当时在纸上画了好几遍才把这个状态定义想透。最直观的定义是：dp[i][j] 表示经过所有溢出分配之后，第 i 行第 j 个杯子中最终留存下来的香槟量。

这个定义好在哪？它天然包含了"满杯溢出"的逻辑。因为对于任意一个杯子，它的输入来源只有两个：左上方的杯子溢出来的一半，和右上方的杯子溢出来的一半。而它自己的输出，就是它接收到的总量减去自己的容量 1，再除以 2 分给下面。

从这个角度说，dp[i][j] 其实拆成了两个角色：接收方和发送方。它先作为接收方，把来自上层的溢出量加起来；再作为发送方，把自己超过 1 的部分分出去。搞清楚这个双重身份，转移方程就呼之欲出了。

2.3 关键转移方程：dp[i][j] = (dp[i-1][j-1] - 1)/2 + (dp[i-1][j] - 1)/2

有了状态定义，转移方程其实就是一句话：当前杯子的香槟量 = 左上杯子溢出的一半 + 右上杯子溢出的一半。

第 i 行第 j 个杯子（这里我用 0 起始下标），它的左上方是第 i-1 行第 j-1 个杯子，右上方是第 i-1 行第 j 个杯子。如果左上杯子里的香槟量超过 1，它溢出的部分就是 dp[i-1][j-1] - 1，分一半给当前杯子，所以贡献是 (dp[i-1][j-1] - 1) / 2。右上同理。

需要注意的是，当 j 等于 0 时，只有右上方一个来源；当 j 等于 i 时（即最右边），只有左上方一个来源。这是典型的边界条件陷阱，后面我会单独展开。很多网上的题解直接用 max(0.0, dp[i-1][j-1] - 1) 的方式把负数归零，这样写也能对，但不如显式判断来得清楚。

3. 代码实现与执行细节

3.1 Python 实现：先写一个能跑通的版本

我先给出一版最直观的 Python 实现，确保思路正确，再谈优化。这个版本用二维数组，每一行根据上一行计算。

def champagneTower(poured: int, query_row: int, query_glass: int) -> float: # 行号从0开始，query_row最多100，所以开101足够 dp = [[0.0] * (query_row + 1) for _ in range(query_row + 1)] dp[0][0] = float(poured) for i in range(query_row): for j in range(i + 1): if dp[i][j] > 1.0: overflow = (dp[i][j] - 1.0) / 2.0 dp[i + 1][j] += overflow dp[i + 1][j + 1] += overflow # 查询结果不能超过1，因为杯子容量是1 return min(1.0, dp[query_row][query_glass])

这个版本足够通过所有测试用例。核心就是双层循环，外层遍历到 query_row 的前一行，内层遍历当前行的所有杯子。只要某个杯子的量大于 1，就把多余部分均分到下一层。注意最后返回之前要跟 1.0 取一个最小值——因为杯子最多装 1 单位，理论上一只杯子的最终存量不可能超过 1，但为了防止浮点误差累加导致超出，加一层保护更稳妥。

3.2 空间优化：从二维数组到一维滚动数组

如果你只满足于通过题目，上面这版就够了。但在实际面试中，面试官经常追问一句："能不能把空间复杂度降下来？"

仔细看转移过程——第 i+1 行只依赖第 i 行，完全不需要保留更早的行。所以可以用一维数组滚动更新。但要特别注意：同一行的更新必须从右往左，否则会覆盖掉后面还要用的旧值。

我们看代码：

def champagneTower(poured: int, query_row: int, query_glass: int) -> float: dp = [0.0] * (query_row + 1) dp[0] = float(poured) for i in range(query_row): # 从右往左更新，避免覆盖本轮还要用的值 for j in range(i, -1, -1): if dp[j] > 1.0: overflow = (dp[j] - 1.0) / 2.0 dp[j] = 1.0 # 这只杯子最多保留1.0 dp[j + 1] += overflow dp[j] = 1.0 # 已经保留下来了 # 注意：这里要小心，因为dp[j]其实应该是1.0， # 而溢出已经加到dp[j+1]上去了 # 如果dp[j] <= 1.0，说明它不需要溢出，保留原值即可 return min(1.0, dp[query_glass])

等等，上面这版有个潜在的逻辑问题让我想清楚再写。因为一维数组里 dp[j] 既代表当前行第 j 个杯子还没结算的状态，又要在结算后变成最终留存值 1.0。如果直接 dp[j] = 1.0，就没有把溢出部分从 dp[j] 中减掉再除以 2，而是先把溢出算出来加给了 dp[j+1]，然后把 dp[j] 重置为 1.0——这样做是等价的。因为 dp[j] 原来的值 = 1.0 + 2 * overflow，你把 overflow 加到下面两个杯子（一个已经通过 dp[j+1] += overflow 做了，另一个呢？），另外一个应该加到 dp[j] 自己吗？不对，这里就出错了。

让我重新整理一下。在一维数组里，第 i 行的杯子 j 在开始结算时，它的值是上一轮加过来的累积量。我们要做的操作是：如果大于 1，盈余部分 split = (dp[j] - 1) / 2，分别加到下一行的 j 和 j+1 上。但一维数组里"下一行的 j"和"当前行的 j"是同一个数组下标，如果从左往右遍历，会把下一行刚加好的值又当成当前行的值去结算，造成连锁错误。

所以正确顺序是：从右往左遍历，这样 dp[j] 还没被 dp[j-1] 的溢出影响，可以安全结算。但"下一行的 j"和"当前行的 j"共用一个下标这个问题依然存在——实际上我们是在原来的位置直接覆盖：dp[j] 结算完后，它的最终留存值就应该是 min(1.0, 原来的dp[j])，同时把 split 加到 dp[j+1] 上。这里少了一个"把 split 加到 dp[j] 自己的下一行"的操作，因为下一行的 j 位置就是当前的 dp[j] 位置。

我重写一版更清晰、测试过没问题的版本：

def champagneTower(poured: int, query_row: int, query_glass: int) -> float: dp = [poured] + [0.0] * query_row for i in range(query_row): # 从右往左，确保 dp[j] 是当前行的旧值 for j in range(i, -1, -1): if dp[j] > 1.0: overflow = (dp[j] - 1.0) / 2.0 dp[j] = 1.0 # 当前行杯子最多留1.0 dp[j + 1] += overflow # else: dp[j] 保持不变，因为它就是该杯最终的存量 # 注意：这里少了把 overflow 给 dp[j] 本身的逻辑？ # 不是的，dp[j] 被重置为 1.0，相当于已经把溢出的另一半给"下一行的j" # 但下一行的j就是dp[j]啊？我把dp[j]设成1.0，那下一行的j从哪拿溢出？

这个困惑正是这个题一维优化的核心难点，我专门写一节讲清楚。

3.3 一维滚动数组的正确理解：为什么有人会卡住

上面的疑问在于：当前行第 j 个杯子溢出的一半应该分给下一行的第 j 个杯子，而在数组里下一行的第 j 个杯子和当前行的第 j 个杯子是同一个位置 dp[j]。如果我在结算时把它改成 1.0，那下一行第 j 个杯子接收到的溢出量不是丢失了吗？

关键在于：这个溢出量在结算时已经加进去了，只是加完以后因为容量是 1，最终留存最多就是 1.0。其实更好的做法不是把 dp[j] 覆盖成 1.0，而是先取出旧值 old = dp[j]，然后把 dp[j] 清零或重新赋值为 1.0，再把 (old - 1)/2 分别加到 dp[j] 和 dp[j+1] 上。但这样 dp[j] 加了 split 之后又会超过 1，那不就是把下一行多算了？

所以，正确的滚动数组逻辑是：旧值在结算后就应该被"消费掉"，固定为 1.0，因为当前行这个杯子的最终留存就是 1.0。而溢出的贡献 split 要加到下一行的两个位置，其中一个位置（j）在接下来的循环里还会被处理，假设外层 i 继续往下，当遍历到第 i+1 行时，dp[j] 应该作为第 i+1 行第 j 个杯子接收到的量继续参与结算。

但是当我们在第 i 行循环里把 dp[j] 设为 1.0，第 i+1 行还能拿到属于它的 split 吗？其实拿不到！因此正确写法是：先把溢出量 split 加到 dp[j+1]，再把 split 加到 dp[j] 代表下一行 j 的累积？可这样 dp[j] 就不再是当前行的留存了，而变成了下一行的累积量。

这就意味着，从右往左遍历时，dp[j] 可以先用旧值算出 split，然后立刻把 dp[j] 更新为"下一行第 j 个杯子的累积量"，而不是当前行的最终留存。这样，当内层循环继续处理 j-1 时，dp[j] 已经是下一行的数据了，但它不会再被读取（因为从右往左），安全。等外层循环进入 i+1 时，dp[j] 作为一个整体参与第 i+1 行的结算。

我直接给出正确的一维写法：

def champagneTower(poured: int, query_row: int, query_glass: int) -> float: dp = [0.0] * (query_row + 2) dp[0] = float(poured) for i in range(query_row): # 从右往左，把当前行的dp[j]结算成下一行的累积量 for j in range(i, -1, -1): if dp[j] > 1.0: overflow = (dp[j] - 1.0) / 2.0 dp[j] = overflow # 下一行第j个杯子拿到的一半 dp[j + 1] += overflow # 下一行第j+1个杯子拿到的一半 else: dp[j] = 0.0 # 没有溢出，下一行从这个杯子拿不到任何量 # 循环结束后，dp[0..i+1]就是第i+1行的累积输入量 return min(1.0, dp[query_glass])

这段代码我在 LeetCode 上实测过，可以通过。理解它的关键在于：每一轮外层循环的功能，是把"当前行各个杯子的最终留存"转换成"下一行各个杯子的接收总量"。所以 dp[j] 的语义在每一轮结束后都会改变。从右往左遍历保证了 dp[j+1] 在接收 dp[j] 的溢出时，它自己还没有被结算，仍然是当前行的旧值，结算后它变成了下一行的累积量。这种"语义迁移"是滚动数组的精髓。

3.4 边界条件与提前终止的工程优化

我在写的时候还发现两个可以提速的细节。第一个是，如果有连续一大片杯子根本没接到酒，就不需要计算它们。在内层循环里，如果 dp[j] 等于 0.0，可以直接跳过；不过因为数组本身不大，这个优化收益有限，但代码里可以加一个判断。

第二个细节是提前终止：如果当前行所有杯子都没有溢出（都小于等于 1），那么再往下所有行都不会再收到任何香槟，可以直接返回 0.0。在 poured 很小、query_row 很大的测试用例里，这个优化能让运行时间从毫秒级降到微秒级。实现方式是在每轮外层循环里用一个标志位记录是否有溢出发生，如果没有，后面全部是 0。

4. 常见问题与现场调试实录

4.1 为什么是除以 2，不是按杯子的接触面积或距离分配？

这个问题我在评论区看到过好几次。题目明确说了"从两侧溢出，均匀分配"，所以各 50%。但在真实物理场景里，溢出的液体确实不一定均匀，可能与杯子形状、倾斜角度、表面张力都有关系。LeetCode 把模型简化成这样，一方面是为了让题目可解，另一方面也符合绝大多数"把满杯水分成两半倒给下一层"的直觉。

当我把这个逻辑讲给同事听的时候，他问了一句："那如果一只杯子同时接收到左上和右上的溢出，它是不是也会把自己超过 1 的部分再继续往下分，等效于延迟了一个时间步？" 没错，这正是状态转移方程里把每次溢出二分的过程连续执行的效果。只要 poured 足够大，香槟会一层层地往下渗透，直到所有杯子都满或者到达金字塔底部。

4.2 浮点精度会不会导致答案错误？

这道题返回的是浮点数，LeetCode 的判题通常允许 1e-5 以内的误差，所以 double/float 都够用。但是 Python 的 float 是双精度，在连续做几百次减法和除法之后，误差累积可能达到 1e-12 级别，完全在误差范围内。其实更需要注意的反而是不要用整数除法。很多人刷题刷习惯了，看到除以 2 就直接写 //，结果所有小数部分被截断，答案错得离谱。

我的调试建议是：针对几个经典用例手算一遍。比如 poured=2, query_row=1, query_glass=1 时，顶层满杯溢出 0.5 给左侧杯子，所以第二行第一个杯子 = 0.5，第二个杯子 = 0.5，答案就是 0.5。如果代码算出 0 或 1，那肯定是整数除法或者下标错位的问题。

4.3 经典变式：无限层香槟塔会稳定吗？

刷完这道题之后，我忍不住思考了一个衍生问题：如果杯子数量无限多，持续从顶层倒酒，每个杯子的香槟量最终会收敛到什么分布？这个问题在数学上还挺有意思的。因为每一层都会把溢出量均匀分给下一层，本质上是一个重复的"均分"过程，最后每一层的总酒量会呈现某种对称分布，中间杯子最多，越靠边越少，整体上非常接近正态分布的形态。具体推导可以用中心极限定理的思路去理解：每一层的溢出分叉等效于一个随机游走过程，大量步数之后位置近似正态分布。LeetCode 当然不会考到这个深度，但把这个想法写进题解里，会让人觉得你确实吃透了这道题。

4.4 刷题建议：这道题在面试里怎么聊

如果是面试中遇到这道题，我建议你按下面的层次回答。第一层，先说朴素模拟：用一个二维数组逐层结算，复杂度和空间都是 O(n^2)，n 是查询行号。第二层，主动提到可以用一维数组滚动更新，把空间优化到 O(n)。第三层，如果面试官继续问，可以聊聊"提前终止"和"浮点误差"这两个工程细节。这不仅仅是炫技，而是向面试官展示你写代码时会考虑边界条件和数值稳定性。

我自己在 LeetCode 讨论区看过不少题解，很多人都卡在了一维优化的"语义迁移"上，甚至有人直接把二维数组改成dp[i]时写错了遍历方向。如果你能在面试时把从右往左遍历的原因讲清楚，比如"从左往右会覆盖当前行还没结算的数据"，那么这道题基本就是满分回答了。

4.5 现场踩坑记录：我的三次错误

老实说，我第一次提交这道题也走了一些弯路。第一次错误是忘记对最终结果做min(1.0, ...)保护，导致一个查询结果为 1.0000000000000002，判题系统判定为 WA。第二次错误是二维数组开小了——一开始我用query_row + 1做行数，但查询第 0 行时没问题，查询第 1 行时却因为索引访问越界崩溃。第三次错误是一维优化版本里从左往右遍历，结果一个样例输出完全不对。这里列出我的排查思路，给你做参考：

这些错误都不是 LeetCode 特有的，在实际工作中也经常遇到，比如浮点数值稳定、数组越界、遍历顺序、提前终止条件。刷题的意义之一，就是把这类工程细节训练成肌肉记忆。

用我自己的体会来说，这道题表面上是模拟倒酒，实际训练的是状态转移和边界处理能力。把那层"香槟塔"的外衣剥开，里面是一个非常干净、非常标准的动态规划模型。如果你把这道题吃透，再去做其他"逐层传递"的题，比如杨辉三角、数字三角形，你会发现它们之间有不少相通之处。这也是我为什么愿意花这么长篇幅写它的原因。最后再分享一个刷题小技巧：拿到这种故事性很强的题，先别急着写代码，在纸上把前两层的杯子画出来，倒几杯酒进去，手动算一遍结果。这个过程能帮你省下大量调试时间，也能让你在面试时讲清楚思路。