JZX轻语：简

LeetCode 799 - 香槟塔

发表于2024年05月08日

#递归 #记忆化搜索

可通过递归的方式，先假设所有的香槟都全部倒进第一层第一个杯子上再溢出，然后自底向上递归计算指定层指定杯子的（溢出前）香槟量。即第i层第j个杯子的香槟量champion[i][j] = 0.5 * champion[i - 1][j - 1] + 0.5 * champion[i - 1][j]（由上一层的两个方向的杯子等量分流）。为了减轻递归的重复计算，可以使用字典来记忆化搜索，当然也可以使用dp计算。

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        buffer = {}

        def getChampagne(row: int, col: int):
            nonlocal buffer

            if col < 0 or col > row:
                return 0

            if row == 0:
                r = poured
            else:
                if (row, col) not in buffer:
                    buffer[(row, col)] = 0.5 * (max(getChampagne(row - 1, col - 1) - 1, 0) +
                                                max(getChampagne(row - 1, col) - 1, 0))
                r = buffer[(row, col)]
            return r

        return min(getChampagne(query_row, query_glass), 1.0)

闪念标签：LC

题目链接：https://leetcode.cn/problems/champagne-tower/