0799. 香槟塔

题目地址(799. 香槟塔)

https://leetcode-cn.com/problems/champagne-tower/

题目描述

我们把玻璃杯摆成金字塔的形状，其中第一层有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:

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)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。