动态规划解香槟塔问题：LeetCode 799题详解

1. 问题背景与题目解析

香槟塔问题源自LeetCode第799题，属于中等难度题型。这道题目模拟了香槟塔中液体流动的物理过程，考察对动态规划或模拟算法的理解和应用能力。题目描述如下：

我们有一个香槟塔，由若干层玻璃杯组成。第一层有1个杯子，第二层有2个杯子，依此类推，第n层有n个杯子。当向顶层杯子倒入一定量的香槟后，液体遵循以下规则流动：

• 当杯子装满（容量为1）时，多余的液体会等量流向下一层相邻的两个杯子
• 这个过程持续直到所有杯子都达到稳定状态

给定倒入的总量poured和查询的杯子位置(row, glass)，需要返回该杯子中的香槟量。

2. 解题思路分析

2.1 问题建模

这个问题可以建模为一个二维的动态规划问题。我们可以将香槟塔看作是一个二维数组dp，其中dp[i][j]表示第i层第j个杯子中的香槟量（层数和杯子编号都从0开始）。

关键观察点：

1. 每个杯子的最大容量为1
2. 溢出的液体会平均分配到下一层的两个相邻杯子
3. 流动过程是自上而下的级联效应

2.2 算法选择

对于这类具有明确状态转移规则的题目，通常有两种解法：

1. 模拟法：直接按照物理过程一步步模拟液体流动
2. 动态规划：利用状态转移方程计算每个杯子的最终状态

考虑到题目需要查询特定杯子的状态，动态规划方法更为高效，时间复杂度为O(n²)，空间复杂度可以通过优化降至O(n)。

3. 动态规划解法详解

3.1 状态定义与转移方程

定义dp[i][j]为第i行第j列杯子中的香槟量。状态转移方程如下：

对于每个杯子(i,j)，如果它接收到的香槟量超过1：

• 保留1单位在杯中
• 将超出部分平均分配到(i+1,j)和(i+1,j+1)杯子中

数学表达式为：

overflow = max(0, dp[i][j] - 1) dp[i][j] -= overflow dp[i+1][j] += overflow / 2 dp[i+1][j+1] += overflow / 2

3.2 实现步骤

1. 初始化一个二维数组dp，尺寸为(query_row+1)×(query_row+1)
2. 将全部香槟倒入顶层杯子：dp[0][0] = poured
3. 从上到下逐层处理：
   • 对于每层的每个杯子，计算溢出量
   • 将溢出量分配到下一层的两个子杯子
4. 返回dp[query_row][query_glass]的值（注意不超过1）

3.3 代码实现（Python）

def champagneTower(poured, query_row, query_glass): 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): overflow = (dp[i][j] - 1.0) / 2.0 if overflow > 0: dp[i+1][j] += overflow dp[i+1][j+1] += overflow return min(1.0, dp[query_row][query_glass])

4. 算法优化与空间复杂度分析

4.1 空间优化技巧

注意到每层的状态只依赖于上一层的状态，可以使用滚动数组将空间复杂度从O(n²)优化到O(n)：

def champagneTower(poured, query_row, query_glass): curr = [poured] for i in range(1, query_row+1): next_row = [0.0] * (i+1) for j in range(len(curr)): overflow = (curr[j] - 1.0) / 2.0 if overflow > 0: next_row[j] += overflow next_row[j+1] += overflow curr = next_row return min(1.0, curr[query_glass])

4.2 时间复杂度分析

两种实现方式的时间复杂度都是O(n²)，其中n为query_row。因为需要处理n层，每层最多有n个杯子。

5. 边界条件与特殊案例

5.1 边界情况处理

1. 当poured=0时，所有杯子都为空
2. 当query_row=0时，只查询顶层杯子
3. 当query_glass不在有效范围内时（虽然题目保证输入有效）
4. 当poured极大时，注意浮点数精度问题

5.2 测试案例示例

# 案例1：倒入1杯，查询(0,0) assert champagneTower(1, 0, 0) == 1.0 # 案例2：倒入2杯，查询(1,1) assert champagneTower(2, 1, 1) == 0.5 # 案例3：倒入100杯，查询(99,99) assert champagneTower(100, 99, 99) == 1.0

6. 常见错误与调试技巧

6.1 典型错误

1. 数组索引越界：忘记香槟塔是金字塔结构，每层杯子数不同
2. 浮点数精度问题：使用浮点数计算时可能产生微小误差
3. 过早截断：在中间层就进行了min(1.0)操作，影响溢出量计算
4. 初始化错误：没有正确初始化dp数组的大小

6.2 调试建议

1. 打印每层的状态，观察液体流动是否符合预期
2. 对小规模案例手动计算验证
3. 特别注意边界杯子的处理（每层的第一个和最后一个杯子）

7. 算法扩展思考

7.1 变种问题

1. 查询整个香槟塔的状态
2. 杯子容量可变的情况
3. 非均匀分配溢出液体
4. 三维香槟塔问题

7.2 实际应用场景

虽然香槟塔问题看似简单，但其核心思想可以应用于：

1. 资源分配系统建模
2. 液体流动模拟
3. 金字塔型数据处理系统
4. 分布式计算中的任务分发

提示：在面试中遇到类似问题时，可以先从小规模案例入手，手动模拟过程，再推导出通用解法。动态规划类问题最重要的是定义清晰的状态和转移方程。