企业官网建设流程全解析

第一次在动态规划题单里看到 LeetCode 799“香槟塔”这道题时，我以为是道脑筋急转弯：不就是一层层倒香槟吗，有什么可考的？真动手写了才发现，题目本身没有任何奇技淫巧，难点全在把“杯子满了往两边流”这个过程，转化成不会算错的状态转移。它的每次出现，都能精准检验一个人对递推模拟的理解是否扎实。

这道题适合谁？我觉得只要你正在为面试复习动态规划、刷题超过五十道但还停留在“一维 DP 套模板”的阶段，或者曾经在周赛里被模拟题卡过，都值得把它仔细做一遍。它不考你背公式，也不考复杂数据结构，只考一件事：你能不能把一个物理过程抽象成递推关系，并且把边界条件处理干净。这种能力恰恰是很多算法题考察的核心，也是我平时面试候选人的时候最愿意看的部分。

1. 题目到底在问什么：一杯满出去，往下层均匀分摊

1.1 题意还原与亲手推演

题目给你的是一座“香槟塔”：第 1 层有 1 个杯子，第 2 层有 2 个杯子，第 3 层有 3 个杯子，以此类推，每层杯子对齐成金字塔形。每个杯子的容量都是 1 杯。现在你从最顶上的杯子连续倒poured杯香槟，杯子满了以后，多余的香槟会均匀地流到下一层左边和右边的两个杯子里。问你最后某个具体位置(query_row, query_glass)的杯子里有多少香槟。

我建议你先别急着写代码，拿小数据手算一遍。比如poured = 4时：

• 顶层杯子直接收到 4，容量只有 1，所以溢出 3，分给第二层两个杯子各 1.5。
• 第二层两个杯子各收到 1.5，都满了，于是各自溢出 0.5。
• 溢出的 0.5 再往下分：第二层左边杯子的 0.5 分给第三层第一个杯子 0.25，第二层右边杯子的 0.5 分给第三层第三个杯子 0.25。
• 第二层两个杯子溢出的香槟都会流到第三层中间的杯子，所以中间杯子收到 0.25 + 0.25 = 0.5。

也就是说，poured = 4时第三层三个杯子里的香槟分别是0.25, 0.5, 0.25。注意它们加起来刚好是 1，也就是第二层两个杯子各自溢出的总量。整个系统里香槟的总量是守恒的，只是有的杯子满了留不住。

这个例子能帮你想清楚一个关键问题：杯子里的最终量，不等于“流经这个杯子的总量”。中间那个杯子总共流入了 0.5，没满，所以最后就是 0.5；第二层的两个杯子各自流入了 1.5，但最后只剩 1，因为多出来的 0.5 已经流走了。

1.2 为什么值得单独写一篇

这道题从算法标签上看只是个“动态规划”，但它在面试里出现频率不低，主要原因是它能把很多人“看起来懂了、一写就错”的毛病暴露出来。刷题指南里提到动态规划，往往先讲背包、最长子序列这类经典题型，而香槟塔属于“模拟型 DP”，没有现成的状态转移模板可套，必须自己从过程里提取递推关系。

它有三个很容易踩的细节：浮点运算、容量封顶、数组边界。这三个细节单独拎出来都不难，但合在一起，就能让一份看似正确的代码在某个测试用例上翻车。我见过不少人第一次写这个题，样例过了，一提交就挂，原因就是没有想清楚“杯子满之后，剩下的香槟必须继续往下走”这个约束。

所以这篇我会从最直观的二维递推开始讲，然后给一维空间优化的写法，再把我实际踩过的坑逐个列出来。这样做完一遍，以后再遇到类似的分流、溢水、传播类题目，你至少能快速建立状态转移的直觉。

2. 从“人肉倒酒”到状态转移：核心思路拆解

2.1 一滴滴模拟？倒一亿杯会直接超时

拿到这个题，脑子里最容易冒出来的朴素想法是：既然香槟是液体，那就一滴一滴地倒，每滴都按规则往下流，最后看看目标杯子里有多少。可行吗？题目里poured可以到10^9，一滴一滴模拟的时间复杂度是 O(poured × 路径长度)，显然不可行。就算不按“滴”来，按“层”来模拟，如果对每个杯子单独枚举香槟从顶层过来的所有路径，路径数量也会随着层数指数增长，因为从顶层到第 n 层中间有大量分叉。

这里就暴露了动态规划的核心思想：把“过程”变成“状态”。从顶层到某个杯子的路径虽然多，但中间的杯子状态是可以复用的。倒香槟是一个层层递进的过程，第 i 层杯子的流入量只与第 i-1 层杯子的溢出量有关。我只需要关心每个杯子“总共流入多少”，而不必关心这些香槟具体是从哪条路径过来的。

2.2 状态定义才是关键：存流入量，不是存剩余量

先说状态定义。用dp[i][j]表示“流经位置(i, j)这个杯子的香槟总量”。注意是流经总量，不是最终剩余量。为什么要这么定义？因为只有知道总流入量，才能算出这个杯子满了之后会溢出去多少；如果定义成“最终剩余量”，那溢出部分就没法继续往下推了。

初始时，顶层杯子收到全部香槟，所以dp[0][0] = poured。对任意杯子(i, j)，如果dp[i][j] > 1，说明杯子满了，溢出的量是dp[i][j] - 1。这些溢出的香槟会均匀分给下一层左右两个杯子：

• 左边杯子(i+1, j)收到(dp[i][j] - 1) / 2
• 右边杯子(i+1, j+1)收到(dp[i][j] - 1) / 2

如果dp[i][j] <= 1，说明杯子还没满，它不会往下流任何香槟，对下一层没有任何贡献。

整个过程从上到下逐层计算，最后目标杯子的答案是min(1.0, dp[query_row][query_glass])。为什么要取min？因为杯子的容量是 1，哪怕流入量是 1.5，最后留在杯子里的也只有 1；如果没有满，那流入量就是剩余量，直接返回即可。

2.3 那个 /2 到底减了什么：容量封顶与溢出转移

很多第一次写这个题的人，会把转移方程写成dp[i+1][j] += dp[i][j] / 2，也就是把当前杯子收到的一半直接分给下一层。这是最典型的错误，因为这样做相当于把“满杯里的香槟”也分出去了。真实情况是：杯子自己要先留住 1 杯，只有超过 1 的部分才需要分配，所以转移前必须先做一次“减 1 封顶”。

我用生活里的例子类比：你往一个杯子里倒水，杯子满了之后水会溢出来，溢出来的部分才会流到下一个容器。你不可能说“杯子里的水倒一半给旁边的杯子”，因为那一半还被杯子装着。香槟塔的每个杯子也是同样道理，只有溢出部分参与分配。

另外要注意，这个题没有“流的顺序”问题。香槟从上层流到下层是同时发生的，但我们在递推时会让上一层的溢出同时更新下一层的两个杯子，累计值不会互相干扰。这种“累加”模式正是 DP 和模拟的关键区别：物理过程是连续的，但状态更新可以按层离散化。

3. 代码实现：从二维 DP 到一维滚动数组

3.1 最直观的二维 DP：完整可运行代码

先把最不容易出错的二维版本写出来。我习惯在 Python 里直接开一个(query_row + 2) × (query_row + 2)的二维数组，多开一列是为了在访问j + 1时不越界。

class Solution: def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float: # 多开一层，避免 i+1 越界 dp = [[0.0] * (query_row + 2) for _ in range(query_row + 2)] dp[0][0] = poured for i in range(query_row + 1): 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 return min(1.0, dp[query_row][query_glass])

这段代码的核心循环只有两层：外层遍历行，内层遍历当前行的每个杯子。每次发现某个杯子的流入量大于 1，就把溢出部分均匀更新到下一层的两个位置。循环最多走到query_row这一层，算完之后目标位置的值已经在dp里了。

这里有一个细节：当i = query_row时，我们其实不需要再往下更新，因为答案已经求出来了。但代码写成range(query_row + 1)也没有问题，因为即使多更新了一层，也不会影响已经算好的目标值，只是多了一点点无用的计算。不过为了严谨和效率，也可以让外层只循环到query_row - 1。

3.2 空间优化：用一维数组滚动更新

二维数组直观，但当query_row很大时，空间开销是O(n²)。实际上这个题的递推关系只涉及“当前行”和“下一行”，完全可以用一维数组滚动更新。我推荐的做法是维护一个dp数组表示当前行，然后用一个临时数组next_row来表示下一行，每算完一层就交换。

class Solution: def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float: dp = [poured] + [0.0] * query_row for i in range(query_row): next_row = [0.0] * (i + 2) for j in range(i + 1): if dp[j] > 1.0: overflow = (dp[j] - 1.0) / 2.0 next_row[j] += overflow next_row[j + 1] += overflow dp = next_row return min(1.0, dp[query_glass])

这里初始的dp长度为query_row + 1，第i次循环里next_row长度是i + 2，正好是下一层应该有的杯子数。当循环结束时，dp就是第query_row层的状态，直接取dp[query_glass]。

有人可能会问：能不能像 01 背包那样原地更新？理论上可以，但顺序非常容易写错，因为下一层的一个杯子会同时收到上一层两个杯子的贡献，如果从左到右原地更新，刚更新的值可能被当成上一层的数据继续参与分配。我自己的经验是，这种模拟型 DP 完全没必要追求最极致的“原地”，用next_row多一个数组，代码清晰且不容易出错，空间复杂度仍然是 O(n)。

3.3 复杂度分析：O(n²) 到底够不够用

时间复杂度方面，两层循环分别遍历到当前行的每一个杯子，三角形区域的杯子总数是1 + 2 + ... + (query_row + 1) = O(n²)，所以时间复杂度是O(n²)。题目里query_row的实际规模一般在一百以内，这个复杂度完全没问题，甚至可以说非常宽松。

空间复杂度：二维版本是O(n²)，一维版本是O(n)。如果你想追求极致，可以只开两个长度为n的数组，但意义不大。真正要留意的是poured能到10^9，这说明过程中许多杯子的流入量会超过 1，浮点数的精度需要保证。好在这个题的判定误差是10^-5，用 Python 的 float（即 C 的 double）完全够用。

我还做过一个小的压力测试：把query_row设成 100，poured设成极大值，跑完一维版本耗时在毫秒级。所以只要不写出指数级递归，基本不用担心性能问题。

4. 调试实录：我踩过的几个坑

4.1 杯子装满了还继续分？最常见的转移方程写错

前面已经提过，最经典的错误是把转移写成dp[i+1][j] += dp[i][j] / 2。第一次写这个题时，我也犯过这个错，样例输出还能对一部分，但一提交就发现结果偏大。原因很简单：dp[i][j]是流入总量，不是溢出量。一个杯子如果只流入了 0.8，它是不会往下滴水的；如果你把 0.4 分给下一层，香槟总量就被凭空放大了。

正确的做法是先把dp[i][j]和容量 1 做比较，只有大于 1 时才计算溢出。这也是这个题最核心的思维转变：分清“流经量”和“溢出量”。我建议在写代码时给变量命名就体现这一点，比如叫overflow，而不是笼统地叫half，这样不容易混淆。

4.2 数组越界与行列长度设计

第二个容易踩的坑是数组越界。二维版本里如果只开(query_row + 1) × (query_row + 1)，当i = query_row、j = i时，访问dp[i + 1][j + 1]就会越界。解决的方案有三个：多开一行一列、循环只走到query_row - 1、在更新前判断边界。最省事的做法就是像我上面那样直接开query_row + 2，多出来的空间不会被使用，但能避免一堆边界判断。

一维版本里同样有这个问题。我在写next_row时，长度是i + 2，因为当前层有i + 1个杯子，下一层有i + 2个杯子。如果你把next_row的长度固定成query_row + 1，后面访问next_row[j + 1]时，j + 1最多也就是query_row，好像不会越界，但会污染后面的数据，因为query_row那一层根本不应该被前面的层写入。所以数组长度跟随层数变化是最稳妥的。

4.3 一维更新的顺序陷阱

我有一次为了省空间，试着用原地更新，结果调了半天都不对。问题出在更新的顺序上：如果从左往右更新dp[j + 1] += overflow，然后下一轮计算j + 1时，dp[j + 1]已经被加上当前层的溢出量，此时再把它当作“上一层杯子的流入量”去计算溢出，就会产生“重复分配”。

举个例子，第一层dp[0] = 4，溢出 1.5 要分给下一层的dp[0]和dp[1]。如果原地从左到右更新，先把dp[0]加上 1.5，然后处理j = 1时可能又把刚加的 1.5 当成已有流入量去分配，逻辑就乱了。

所以我的建议是：不要试图在香槟塔上做原地更新，老老实实用一个next_row。空间优化是为了降低复杂度，不是为了炫技，清晰正确永远排在第一位。

4.4 浮点误差和提前返回

还有两个小的细节。第一个是浮点误差：当你判断dp[i][j] > 1.0时，理论上流入量可能恰好是 1.0，但因为浮点运算误差可能变成 0.9999999999 或 1.0000000001。前者会导致本应溢出的香槟没被分配，后者则会让一个根本没满的杯子被判断为溢出。实际做题时，这个误差对最终结果影响微乎其微，因为判定允许10^-5的误差，不需要过度纠结。

第二个是提前剪枝：如果在某一层发现所有杯子的流入量都不超过 1，那说明这一层没有任何溢出，再往下也不会再有香槟了。如果目标行还没到，可以直接返回 0。这个优化在某些测试用例里能省不少计算，但前提是你得在每层循环结束后判断一下最大值。我平时会加这个剪枝，尤其是当poured比较小而query_row比较大时，能明显加快速度。

5. 这题还能怎么考：模式识别与变体

5.1 怎么一眼识别这类模拟 DP

香槟塔这类题的典型特征是：状态在结构上逐层扩散，每个位置的结果由上一层相邻位置的某种运算决定。你可以把它理解成一个“带容量限制的杨辉三角”：杨辉三角里每个数字由左上方和右上方的数字相加，而香槟塔里每个杯子由左上方和右上方的溢出量累加，只是每个杯子还会先“截留”一部分。

以后看到以下关键词，可以优先往“模拟型 DP”上想：

• 有明确的层级结构或网格结构，状态只能向下或向右传递
• 每个节点的输出会分裂成多个方向
• 每个节点有容量限制或阈值，超过阈值才会继续传播
• 最后只问某个具体位置的最终值，而不是整条路径

这类题不要求你推导出华丽的公式，但要求你抽象出“状态”和“转移规则”。识别出这一点，比记住某个特定题目的代码重要得多。

5.2 如果题目换个问法：二分答案与反向推理

香槟塔的原始问法是“倒poured杯，求某个杯子有多少”。面试时面试官很可能换个角度问你：“至少需要倒多少杯，才能让(query_row, query_glass)这个杯子有香槟？”或者“至少倒多少杯，这个杯子才是满的？”

这种问法可以用二分答案解决。poured的范围很大，但答案具有单调性：倒得越多，目标杯子里的香槟越多。于是可以对poured做二分，每次调用同一个模拟函数，检查目标杯子的值是否达到某个阈值。由于每次 check 的复杂度是O(n²)，总复杂度是O(n² log M)，其中M是二分上界。这个思路在面试里很好用，因为它展示了你对算法复杂度和单调性的理解。

还有一种反向推法：假设目标是让(query_row, query_glass)最终有x杯香槟，那么可以倒推它需要从上层两个杯子获得多少溢出量。由于一个杯子的溢出量和它的流入量有直接关系，你可以从目标杯子反推上游杯子至少需要多少流入量。这个方法写起来比正向 DP 更绕，因为同一个上层杯子可能被多个目标路径共用，需要计算的是满足并发需求的足够量。我个人觉得正向模拟加二分明显更好理解，面试时建议先说正向思路，再主动补充“反过来的问题可以用二分做”，能加分不少。

5.3 跟其他题目的血脉联系：杨辉三角、水流与概率

香槟塔不是孤立的一道题。往大了说，它和杨辉三角、概率传播、水流模拟都有联系。

如果把香槟塔的容量限制去掉，也就是假设所有杯子都不满，那么每个杯子收到的量就是组合数乘上某个比例，本质上就是杨辉三角的系数分布。满杯限制相当于给每个节点做了“截断”，导致分布不再严格符合组合数。理解这一点，能帮你更快地理解为什么 DP 数组里的数字是那样变化的。

另外，有一类概率 DP 题和它非常像：比如一个小球从顶层落下，碰到一个钉子后各有 1/2 概率弹向左右，问落到某个位置的概率。这类题的状态转移方程和香槟塔一模一样，只是把“溢出量的一半”换成了“概率乘 2”，把容量限制去掉。你如果能把香槟塔的递推写明白，这类概率题基本可以秒解。

还有一个经典的水流模拟题：给定一个水槽结构，水从顶部灌入，问底部某个位置是否会有水流出。这本质上也是“有容量、有分流”的递推模拟，只不过结构不再是规整的三角形。所以我说香槟塔的价值不在题目本身，而在它背后的建模方式。

6. 实战复盘：我从这题中提炼的做题模板

6.1 一套通用的递推模拟框架

做完这道题之后，我给自己总结了一套做“模拟型 DP”的通用流程，现在分享给你。

第一步，明确状态。不要急着写代码，先问自己：我需要记录什么信息才能推出下一步？香槟塔里需要记录的是“每个杯子当前流入了多少”，也就是流入总量。没有这个值，你无法判断溢出量。

第二步，写转移方程。转移一般来自题目描述的物理规律，香槟塔的转移就是“超过容量的部分均分给下一层左右两杯”。写转移方程时，一定要把“什么量参与转移、什么量被节点保留”分清楚。这个步骤如果出错，后面所有代码都白搭。

第三步，确定循环顺序和边界。大多数递推模拟都是从上到下、从内到外，按层级顺序推进。边界包括数组大小、循环的终止条件、是否需要在最后做封顶处理。香槟塔里最容易漏的就是最后对答案取min(1.0, ...)。

第四步，考虑能否优化空间。优化不是必须的，但如果递推只依赖相邻层，一维滚动数组通常能省下不少内存。优化前先保证二维版本正确，再逐步压缩。

6.2 给刷题者的自查清单

如果你准备把这道题写进自己的刷题笔记，我建议你在提交前对照下面这个清单自查一遍：

• 转移公式里，我是不是把流入量直接当成溢出量分配了？
• 目标杯子的答案有没有取容量上限 1？
• 数组空间是否足够容纳j + 1的访问？
• 一维滚动数组的层间交换是否正确，有没有污染上一层的值？
• 浮点数计算有没有用 double/float，而不是整数？
• 如果poured小于query_row，我是否做了提前返回的处理？

这几个问题覆盖了这道题 90% 的坑。我自己后来又在不同时间把这道题重做了两遍，第一遍复习二维 DP，第二遍专练一维滚动数组加提前剪枝，每次都能发现一些新的细节。经典题值得反复做，因为它能帮你把“边界条件”“状态定义”“空间优化”这些基本功练扎实。

如果你最近也在刷动态规划专题，或者正准备面试，我强烈建议你把香槟塔加进自己的必做清单。它不像背包那样有固定模板，也不像图论那样需要大量前置知识，但它用最简单的方式逼你理解“递推”的本质：你的当前状态，是由哪些前序状态以什么规则叠加出来的。把这个想清楚了，后面遇到任何复杂的 DP 题，你至少不会一开始就走偏。