题目

我们把玻璃杯摆成金字塔的形状，其中 第一层 有 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^9
0 <= query_glass <= query_row < 100

解题思路

我们可以把这道题看作是一个 有向无环图（DAG）上的流量传播问题，或者更具体地说，是一个 带阈值激活函数的卷积过程。

1. 核心模型：帕斯卡三角（Pascal's Triangle）变体

首先，物理结构是一个金字塔，索引方式完全对应帕斯卡三角：

顶层是 (0, 0)。
下一层是 (1, 0), (1, 1)。
再下一层是 (2, 0), (2, 1), (2, 2)。

2. 核心思想：“推（Push）” 优于 “拉（Pull）”

在动态规划中，通常有两种状态转移思维：

Pull（拉）： 为了算当前格子，去问上面的格子“给了我多少”。
Push（推）： 当前格子算完了，把多余的“推”给下面的格子。

对于这道题，“推”的逻辑要清晰得多。 为什么？

因为每个杯子的溢出量取决于它自己当前的存量。如果用“拉”的逻辑，你需要反向去推导上面两个杯子分别溢出了多少，逻辑会很绕。

3. 算法流程分解

我们可以把整个过程想象成 “分层结算”：

第一步：初始化（注入能量）

我们不再一滴一滴地模拟时间流逝（那太慢了）。
我们假设时间静止，先把所有的香槟 poured 全部一股脑倒进顶层杯子 (0, 0) 里。
此时，dp[0][0] = poured。这个值可能巨大（比如 100），没关系，这代表“流经这里的总流量”。

第二步：层级传播（Forward Pass）

从上往下，一层一层处理。对于每一个杯子 (r, c)，我们执行以下逻辑：

检查阈值（Activation）：
- 如果杯子里的量 X <= 1：它完全兜住了，没有东西流下去。
- 如果杯子里的量 X > 1：它装满 1 单位，剩下的 X - 1 必须流走。
流量分配（Distribution）：
- 流走的量是 overflow = X - 1。
- 根据物理规则，均匀分给它的两个“孩子”节点：
  - 左下方孩子 (r+1, c) 接收 overflow / 2。
  - 右下方孩子 (r+1, c+1) 接收 overflow / 2。
状态更新：
- 不仅要更新孩子节点，理论上当前节点 (r, c) 处理完后应该变成 1。
- 但在代码实现中，为了节省操作，我们甚至不需要修改当前节点的值，只管把溢出值累加到下一层数组里即可。

第三步：终止与截断（Clamping）

我们只需要模拟到第 query_row - 1 行，第 query_row 行的数据就已经被上面的行“推”算出来了。
最后一步校验：题目问的是“杯子里有多少酒”。因为我们的 dp 数组存储的是“流经的总流量”，可能算出来 dp[query_row][query_glass] = 5.5。
既然杯子容量只有 1，那么结果就是 min(1, 5.5) = 1。

总结公式

$$dp[r+1][c] \ += \ \max(0, \frac{dp[r][c] - 1}{2})$$

$$dp[r+1][c+1] \ += \ \max(0, \frac{dp[r][c] - 1}{2})$$

这就是这道题的核心逻辑。它利用了 无后效性（上一层的处理结果完全决定了下一层的输入），非常适合动态规划。

##具体代码

func champagneTower(poured int, query_row int, query_glass int) float64 {
	// 优化 1：空间复杂度 O(R)。
	// 我们只需要维护当前这一行的状态。初始第一层只有 1 个杯子。
	row := []float64{float64(poured)}

	// 优化 2：减少不必要的计算。
	// 我们只需要从第 0 层模拟流向第 query_row 层。
	// 当 r = query_row - 1 时，计算出的 nextRow 就是我们要找的 query_row 层。
	for r := 0; r < query_row; r++ {
		// 下一层比当前层多一个杯子
		nextRow := make([]float64, len(row)+1)

		// 遍历当前层的每一个杯子，计算流向下一层的量
		for i, volume := range row {
			if volume > 1 {
				// 溢出部分 = (总量 - 1) / 2
				flow := (volume - 1) / 2.0
				nextRow[i] += flow
				nextRow[i+1] += flow
			}
		}
		// 滚动更新：下一层变为当前层，进入下一次循环
		row = nextRow
	}

	// 此时 row 切片存储的正是第 query_row 层的数据
	// 优化 3：使用 math.Min 处理结果
	return math.Min(1, row[query_glass])
}

799. 香槟塔

beautifulremi

题目