# 0799. 香槟塔
### 题目地址(799. 香槟塔)
### 题目描述
```
我们把玻璃杯摆成金字塔的形状，其中第一层有1个玻璃杯，第二层有2个，依次类推到第100层，每个玻璃杯(250ml)将盛有香槟。
从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）
例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟，如下图所示。
现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（i 和 j都从0开始）。
示例 1:
输入: poured(倾倒香槟总杯数) = 1, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.0
解释: 我们在顶层（下标是（0，0））倒了一杯香槟后，没有溢出，因此所有在顶层以下的玻璃杯都是空的。
示例 2:
输入: poured(倾倒香槟总杯数) = 2, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.5
解释: 我们在顶层（下标是（0，0）倒了两杯香槟后，有一杯量的香槟将从顶层溢出，位于（1，0）的玻璃杯和（1，1）的玻璃杯平分了这一杯香槟，所以每个玻璃杯有一半的香槟。
注意:
poured 的范围[0, 10 ^ 9]。
query_glass 和query_row 的范围 [0, 99]。
```
### 前置知识
* 动态规划
* 杨辉三角
### 公司
* 暂无
### 思路
这道题和杨辉三角问题类似，实现的基本思路都是从上到下模拟。如果大家对杨辉三角问题不熟悉，建议先看下杨辉三角。杨辉三角也是动态规划中很经典的问题。
由题目可知杯子的数目是第一行一个，第二行两个。。。第 i 行 i 个 (i >= 1)。因此建立一个二维数组即可。为了简单，我们可以建立一个大小为 R \_ R 的二维矩阵 A ，其中 R 为香槟塔的高度。虽然这样的建立方式会造成一半的空间浪费。但是题目的条件是\*\* query\_glass 和 query\_row 的范围 \[0, 99]\*\*，因此即便如此问题也不大。当然你也可以直接开辟一个 100 \_ 100 的矩阵。
 （用 R \* R 的二维矩阵 A 进行模拟，如图虚线的部分是没有被使用的空间，也就是”浪费“的空间）
接下来，我们只需要按照题目描述进行模拟即可。具体来说：
* 先将第一行第一列的杯子注满香槟。即 A\[0]\[0] = poured
* 接下来从上到下，从左到右进行模拟。
* 模拟的过程就是
1. 计算溢出的容量
2. 将溢出的容量平分到下一层的两个酒杯中。（只需要平分到下一层即可，不用关心下一层满之后的溢出问题，因为之后会考虑，下面的代码也会体现这一点）
### 关键点
* 不必模拟多步，而是只模拟一次即可
### 代码
* 语言支持：Python3
Python3 Code:
```py
class Solution:
def champagneTower(self, poured, R, C):
# 这种初始化方式有一半空间是浪费的
A = [[0] * (R+1) for _ in range(R+1)]
A[0][0] = poured
# 从上到下，从左到右模拟每一行每一列
for i in range(R + 1):
for j in range(i+1):
overflow = (A[i][j] - 1.0) / 2.0
# 不必模拟多步，而是只模拟一次即可。也就是说我们无需溢出到下一层之后，下一层的杯子容量大于 1，因为我们后面处理即可，这和直觉上或许有所不一样。体现在代码上只需要 if 即可，无需 while
if overflow > 0 and i < R and j <= C:
A[i+1][j] += overflow
if j+1<=C: A[i+1][j+1] += overflow
return min(1, A[R][C]) # 最后的结果如果大于 1，说明流到地板上了，需要和 1 取最小值。
```
**复杂度分析**
* 时间复杂度：$O(R^2)$
* 空间复杂度：$O(R^2)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/799.champagne-tower.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.