发表于 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 题目链接