# 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
