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 行开始逐层往下结算。每一只杯子的计算逻辑是这样的如果 dp[i][j] 小于等于 1说明这只杯子没满也没有多余的香槟可以往下传递直接跳过。如果 dp[i][j] 大于 1说明这只杯子已经满了它自己保留 1 单位剩余部分 divided (dp[i][j] - 1) / 2 分别加到下一层的 dp[i1][j] 和 dp[i1][j1] 上。由于每一行最多只有 i1 个杯子而查询的行号 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 空间优化从二维数组到一维滚动数组如果你只满足于通过题目上面这版就够了。但在实际面试中面试官经常追问一句能不能把空间复杂度降下来仔细看转移过程——第 i1 行只依赖第 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[j1]上去了 # 如果dp[j] 1.0说明它不需要溢出保留原值即可 return min(1.0, dp[query_glass])等等上面这版有个潜在的逻辑问题让我想清楚再写。因为一维数组里 dp[j] 既代表当前行第 j 个杯子还没结算的状态又要在结算后变成最终留存值 1.0。如果直接 dp[j] 1.0就没有把溢出部分从 dp[j] 中减掉再除以 2而是先把溢出算出来加给了 dp[j1]然后把 dp[j] 重置为 1.0——这样做是等价的。因为 dp[j] 原来的值 1.0 2 * overflow你把 overflow 加到下面两个杯子一个已经通过 dp[j1] overflow 做了另一个呢另外一个应该加到 dp[j] 自己吗不对这里就出错了。让我重新整理一下。在一维数组里第 i 行的杯子 j 在开始结算时它的值是上一轮加过来的累积量。我们要做的操作是如果大于 1盈余部分 split (dp[j] - 1) / 2分别加到下一行的 j 和 j1 上。但一维数组里下一行的 j和当前行的 j是同一个数组下标如果从左往右遍历会把下一行刚加好的值又当成当前行的值去结算造成连锁错误。所以正确顺序是从右往左遍历这样 dp[j] 还没被 dp[j-1] 的溢出影响可以安全结算。但下一行的 j和当前行的 j共用一个下标这个问题依然存在——实际上我们是在原来的位置直接覆盖dp[j] 结算完后它的最终留存值就应该是 min(1.0, 原来的dp[j])同时把 split 加到 dp[j1] 上。这里少了一个把 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[j1] 上。但这样 dp[j] 加了 split 之后又会超过 1那不就是把下一行多算了所以正确的滚动数组逻辑是旧值在结算后就应该被消费掉固定为 1.0因为当前行这个杯子的最终留存就是 1.0。而溢出的贡献 split 要加到下一行的两个位置其中一个位置j在接下来的循环里还会被处理假设外层 i 继续往下当遍历到第 i1 行时dp[j] 应该作为第 i1 行第 j 个杯子接收到的量继续参与结算。但是当我们在第 i 行循环里把 dp[j] 设为 1.0第 i1 行还能拿到属于它的 split 吗其实拿不到因此正确写法是先把溢出量 split 加到 dp[j1]再把 split 加到 dp[j] 代表下一行 j 的累积可这样 dp[j] 就不再是当前行的留存了而变成了下一行的累积量。这就意味着从右往左遍历时dp[j] 可以先用旧值算出 split然后立刻把 dp[j] 更新为下一行第 j 个杯子的累积量而不是当前行的最终留存。这样当内层循环继续处理 j-1 时dp[j] 已经是下一行的数据了但它不会再被读取因为从右往左安全。等外层循环进入 i1 时dp[j] 作为一个整体参与第 i1 行的结算。我直接给出正确的一维写法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 # 下一行第j1个杯子拿到的一半 else: dp[j] 0.0 # 没有溢出下一行从这个杯子拿不到任何量 # 循环结束后dp[0..i1]就是第i1行的累积输入量 return min(1.0, dp[query_glass])这段代码我在 LeetCode 上实测过可以通过。理解它的关键在于每一轮外层循环的功能是把当前行各个杯子的最终留存转换成下一行各个杯子的接收总量。所以 dp[j] 的语义在每一轮结束后都会改变。从右往左遍历保证了 dp[j1] 在接收 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 就直接写 //结果所有小数部分被截断答案错得离谱。我的调试建议是针对几个经典用例手算一遍。比如 poured2, query_row1, query_glass1 时顶层满杯溢出 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 行时却因为索引访问越界崩溃。第三次错误是一维优化版本里从左往右遍历结果一个样例输出完全不对。这里列出我的排查思路给你做参考错误现象可能原因排查方式结果略大于 1浮点误差累积返回前min(1.0, ans)数组越界行数/列数开少了统一开query_row 1并检查边界分支一维结果混乱遍历方向错误查看从右往左的覆盖关系画数组状态图小数全被截断用了整数除法检查是否写成//除法前转为 float大样例超时没有提前终止加溢出标志位无溢出直接返回这些错误都不是 LeetCode 特有的在实际工作中也经常遇到比如浮点数值稳定、数组越界、遍历顺序、提前终止条件。刷题的意义之一就是把这类工程细节训练成肌肉记忆。用我自己的体会来说这道题表面上是模拟倒酒实际训练的是状态转移和边界处理能力。把那层香槟塔的外衣剥开里面是一个非常干净、非常标准的动态规划模型。如果你把这道题吃透再去做其他逐层传递的题比如杨辉三角、数字三角形你会发现它们之间有不少相通之处。这也是我为什么愿意花这么长篇幅写它的原因。最后再分享一个刷题小技巧拿到这种故事性很强的题先别急着写代码在纸上把前两层的杯子画出来倒几杯酒进去手动算一遍结果。这个过程能帮你省下大量调试时间也能让你在面试时讲清楚思路。