# 799.香槟塔

[799. 香槟塔](https://leetcode.cn/problems/champagne-tower/)

## 线性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`

```python
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)
```