799. Champagne Tower

📘 題目敘述

你有把香檳倒進一座香檳塔。這座塔的排列方式是：第 0 列有 1 個杯子，第 1 列有 2 個杯子，第 2 列有 3 個杯子，以此類推。

每個杯子最多只能裝 1 杯香檳。當某個杯子的香檳超過 1 時，多出來的部分會平均分到它正下方相鄰的兩個杯子（左下、右下）。

你倒入了 poured 杯香檳。

請回傳在香檳倒完之後，第 query_row 列、第 query_glass 個杯子裡面實際裝了多少香檳。

答案必須在 10^-5 以內視為正確。

條件限制

0 <= poured <= 10^9
0 <= query_row <= 100
0 <= query_glass <= query_row

🧠 解題思路

這題我用 DP 直接模擬「每一杯溢出的量會往下分流」的過程。

我把 ml[i][j] 定義成：第 i 列第 j 個杯子目前被倒進來的香檳總量（可能超過 1）。

因為每個杯子最多只留 1 杯，多出來的部分才會往下流，所以我在處理每個杯子時只在乎：

overflow = max(0, ml[i][j] - 1)

如果 overflow > 0：

左下杯子會得到 overflow / 2
右下杯子會得到 overflow / 2

我只需要一路算到 query_row 就好，因為題目只問那一層的某個杯子。

最後答案要回傳「實際裝了多少」，所以還要再做一次：

min(ml[query_row][query_glass], 1.0)

因為杯子最多只能裝 1。

所有變數

ml：DP 表，ml[i][j] 代表第 i 列第 j 個杯子累積被倒到的香檳量
k：某個杯子溢出的香檳量（ml[i][j] - 1 的正值部分）

🪜 主要流程步驟

1. 建立 DP 表並把 poured 倒在頂端

我先開一個大小到 query_row 的 2D 陣列，因為更下面的列我不需要算。

然後把 ml[0][0] = poured，代表所有香檳先倒進最上面那一杯。

2. 逐列往下推，把溢出的量平均分到下一列

我從第 0 列推到第 query_row - 1 列。

對每個杯子 (i, j)：

算 k = max(0.0, ml[i][j] - 1.0)
如果 k > 0
- ml[i + 1][j] += k / 2
- ml[i + 1][j + 1] += k / 2

這樣下一列的杯子就會累積到所有從上面流下來的量。

3. 回傳 query_row, query_glass 的實際裝量

DP 算完後 ml[query_row][query_glass] 可能大於 1，但杯子最多只能裝 1。

所以回傳：

min(ml[query_row][query_glass], 1.0)

💻 程式碼實作

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<vector<double>> ml(query_row + 1, vector<double>(query_row + 1, 0.0));
        ml[0][0] = (double)poured;
        for (int i = 0; i < query_row; i++) {
            for (int j = 0; j <= i; j++) {
                double k = max(0.0, ml[i][j] - 1.0);
                if (k > 0) {
                    ml[i + 1][j] += k / 2.0;
                    ml[i + 1][j + 1] += k / 2.0;
                }
            }
        }
        return min(ml[query_row][query_glass], 1.0);
    }
};

🔗 題目連結

https://leetcode.com/problems/champagne-tower/