What is the main algorithm pattern used in Champagne Tower?

This problem is solved using state transition dynamic programming, tracking overflow from each glass to the next row.

How do I handle a glass that receives more than 1 cup?

Always cap the amount at 1 for the queried glass and propagate any excess to the two glasses below it equally.

Can I optimize space usage for large query rows?

Yes, using a rolling 1D DP array per row reduces space from O(R^2) to O(R) while maintaining correct overflow calculations.

Why does pouring a small amount sometimes leave lower glasses empty?

Because champagne only flows when the glass above exceeds 1 cup, so insufficient poured amounts don’t reach deeper rows.

Is recursion a good approach for Champagne Tower?

Pure recursion without memoization is inefficient; using iterative DP with state transitions is the preferred method.

#799

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

香槟塔

我们把玻璃杯摆成金字塔的形状，其中第一层有 1 个玻璃杯，第二层有 2 个，依次类推到第 100 层，每个玻璃杯将盛有香槟。从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子…

动态规划

题目描述

我们把玻璃杯摆成金字塔的形状，其中 第一层 有 1 个玻璃杯， 第二层 有 2 个，依次类推到第 100 层，每个玻璃杯将盛有香槟。

从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）

例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟，如下图所示。

现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（ i 和 j 都从0开始）。

示例 1:
输入: poured(倾倒香槟总杯数) = 1, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.00000
解释: 我们在顶层（下标是（0，0））倒了一杯香槟后，没有溢出，因此所有在顶层以下的玻璃杯都是空的。

示例 2:
输入: poured(倾倒香槟总杯数) = 2, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.50000
解释: 我们在顶层（下标是（0，0）倒了两杯香槟后，有一杯量的香槟将从顶层溢出，位于（1，0）的玻璃杯和（1，1）的玻璃杯平分了这一杯香槟，所以每个玻璃杯有一半的香槟。

示例 3:

输入: poured = 100000009, query_row = 33, query_glass = 17
输出: 1.00000

提示:

0 <= poured <= 10⁹
0 <= query_glass <= query_row < 100

lightbulb

解题思路

方法一：模拟

我们直接模拟倒香槟的过程。

定义一个二维数组 $f$ ，其中 $f[i][j]$ 表示第 $i$ 层第 $j$ 个玻璃杯中的香槟量。初始时 $f[0][0] = poured$ 。

对于每一层，如果当前杯子的香槟量 $f[i][j]$ 大于 $1$ ，香槟会流向下一层的两个杯子，流入的量为 $\frac{f[i][j]-1}{2}$ ，即当前杯子的香槟量减去 $1$ 后除以 $2$ ，然后当前杯子的香槟量更新为 $1$ 。

模拟结束，返回 $f[query\_row][query\_glass]$ 即可。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 为层数，即 $\text{query\_row}$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        f = [[0] * 101 for _ in range(101)]
        f[0][0] = poured
        for i in range(query_row + 1):
            for j in range(i + 1):
                if f[i][j] > 1:
                    half = (f[i][j] - 1) / 2
                    f[i][j] = 1
                    f[i + 1][j] += half
                    f[i + 1][j + 1] += half
        return f[query_row][query_glass]

speed

复杂度分析

指标	值
时间	complexity is O(R^2) since every glass up to the query row is processed once. Space complexity is O(R^2) to store DP states for all glasses up to the query row.
空间	O(R^2)

psychology

面试官常问的追问

外企场景

question_mark
Emphasize using dynamic programming to track cascading state transitions in the pyramid.
question_mark
Look for correct handling of overflow splitting exactly half to each child glass.
question_mark
Notice if the candidate caps values at 1 per glass instead of summing total overflow incorrectly.

warning

常见陷阱

外企场景

error
Failing to distribute overflow correctly, leading to inaccurate amounts in lower glasses.
error
Not capping the queried glass at 1, returning more than the glass can hold.
error
Attempting a recursive solution without memoization, causing excessive computation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute total full glasses after pouring a given amount, leveraging the same DP overflow approach.
arrow_right_alt
Determine the first glass to overflow beyond 1 cup in a large poured scenario using DP simulation.
arrow_right_alt
Optimize space by using a single-row rolling DP array for large query_row values.

help

常见问题

外企场景

继续练习

#801 使序列递增的最小交换次数 #805 数组的均值分割 #792 匹配子序列的单词数