力扣-799. 香槟塔

题目描述

思路及实现

OK看到这种题目首先我的思路就是找规律，先把每层数字列一下先：

以及在倒入香槟的时候千万别把自己套进去了，我就是把自己套进去想着香槟一瓶一瓶倒下去再分配，结果压根没想到怎么做，其实一次性倒在最上边的杯子上，溢出了就往下分，效果是一样的。
现在已经找到规律了，那么跟着规律走就容易出思路了。看到左边的图，可以发现我写出了两种下标，其实也可以说对应两种方法。

直接计算法

OK那么这里我想说的是，我在画这张图的时候还没发现他是从0开始计数的，所以在写代码的时候row变成了从0开始而不是1，所以后续手动补上+1，也因为这个原因代码看上去可能比较乱，比较难读，果咩那塞！

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

计算每行法

可以看到啊，其实这就是官解的思路和代码，非常简洁明了且快速。

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        v = [poured]
        for n in range(1, query_row + 1):
            next_v = [0] * (n + 1)
            for i in range(len(v)):
                if v[i] > 1:
                    next_v[i] += (v[i] - 1) / 2
                    next_v[i + 1] += (v[i] - 1) / 2
            v = next_v
        return min(1, v[query_glass])

---

希望本文章能够帮到您~