799.香槟塔

799. 香槟塔

线性dp

为了方便，我们令 poured 为 k，query_row 和 query_glass 分别为 m和 n。

定义f[i][j]为第 i 行第 j 列杯子所经过的水的流量（而不是最终剩余的水量）。

起始我们有 f[0][0]=k，最终答案为 min⁡(f[m][n],1)。

不失一般性考虑 f[i][j]能够更新哪些状态：显然当 f[i][j]不足 1的时候，不会有水从杯子里溢出，即 f[i][j]将不能更新其他状态；当 f[i][j] 大于 1 时，将会有 f[i][j]−1 的水会等量留到下一行的杯子里，所流向的杯子分别是「第 i+1 行第 j列的杯子」和「第 i+1行第 j+1列的杯子」，增加流量均为(f[i][j]−1)/2 。

即有 f[i+1][j] = (f[i][j]−1)/2 和 f[i+1][j+1] = (f[i][j]−1)/2

class Solution:
    def champagneTower(self, k: int, m: int, n: int) -> float:
        dp = [[0] * (m + 2) for _ in range(m + 2)]  # 状态矩阵，只用到下三角
        dp[0][0] = k
        for i in range(m + 1):
            for j in range(i + 1):
                if dp[i][j] <= 1:
                    continue
                dp[i + 1][j] += (dp[i][j] - 1) / 2
                dp[i + 1][j + 1] += (dp[i][j] - 1) / 2
        return min(dp[m][n], 1)