LeetCode 799. 香槟塔
题目描述
✅ 799. 香槟塔
题意分析
每个杯子的容量都是
1，装满后多余的香槟平均流向下一行相邻的两个杯子。行号、杯子编号都从零开始，第r行有r + 1个杯子，要求指定杯子最终装了多少。不能只记录杯子当前最多为
1的留存量，因为超过容量的部分还要继续向下传。先记录每杯收到的总流入量，再由它计算溢出和最终留存。
解法：动态规划模拟
核心思路
[!blue]
定义
dp[r][c]为第r行第c个杯子收到的香槟总量，它可以大于1。初始只有顶杯直接收到倒入的香槟，所以dp[0][0] = poured，其余状态为零。处理一个杯子时，若流入不超过
1，它会全部留下，不向下传播；若超过1，多出的部分才会流走。统一写成overflow = max(dp[r][c] - 1, 0)，下方的(r + 1, c)和(r + 1, c + 1)各收到overflow / 2。同一杯可能同时收到左上方和右上方两个父杯的贡献，所以更新下一行必须累加，不能覆盖。按行从上往下处理时，当前行所有父杯都已处理完，
dp[r][c]已包含完整流入，再计算溢出就不会漏算某个方向后到的香槟。这个转移恰好对应每个杯子的容量限制和平均分流规则，且酒量只会从上一行流向下一行，因此逐行计算就能得到每杯最终的总流入。查询杯真正留下的量是
min(1, dp[queryRow][queryGlass])；必须在计算其下游溢出之前保留完整流入，不能把状态预先截成1。
解题步骤
- 顶杯放入全部香槟。
- 按行传播正溢出。
- 返回查询位置流入量与一的较小值。
当前代码也会处理查询行，并向下一行写入，因此数组分配到
queryRow + 1行，也就是总共queryRow + 2行。poured == 0时所有状态保持零，查询顶杯时直接得到倒入量与1的较小值。分流可能产生小数，Java 使用double、Go 使用float64保存状态。
代码实现
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+1)^2)$，r 为查询行。
- 空间复杂度：$O((r+1)^2)$，二维流入表。
关键点总结
[!green]
- 流入量与留存量不同，传播依据前者。
- 每层只影响下一层，依赖顺序明确。
- 当前循环还会从查询行向下传播，因此数组额外分配一行；只处理查询行之前的层也能得到答案。
易错点总结
[!yellow]
- 顶杯先截到一，会丢掉全部溢出。
- 下层使用覆盖赋值，会漏掉另一个父杯。
- 传播负差值，会产生不可能的负酒量。
- Java 先将溢出截成非负再判断；Go 使用原始差值，必须在差值为正时才传播。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 118. 杨辉三角 | 简单 | 同样按三角形父子位置递推，但本题只有超出杯子容量的部分才向下分流。 |