解題區►Leetcode►Medium

Leetcode 799 - Champagne Tower

題目

Problem#

題目說有 n 個杯子，從最上面的那個杯子開始倒水，總共倒 p 杯水，每個杯子只要到一杯就滿，往滿的水杯中倒水會往兩側溢出 1/2 的水，
給你倒水的總杯數 p 問你第 r 列第 c 個的水杯的狀態。

  • 0 <= p <= 109
  • 0 <= r <= c < 100

想法#

從最上面那杯開始倒水，可以一次倒全部的水，假如一杯水杯超過 1.0，就往兩側倒 (b[i]-1)/2 的水
可以用一個二維陣列維護 dp[r][c] 的水量，一杯水(dp[i][j])中的水來自其左上(dp[i-1][j-1])和右上(dp[i-1][j])的水漏下來
接著就模擬一次流水即可。

  • 時間複雜度: $\mathcal{O}(N^2)$
    • 只要掃一遍所有的水杯就倒完了
  • 空間複雜度: $\mathcal{O}(N^2)$

AC Code#

賞析#

  • top-down 作法

  • 另一個 bottom up 作法 跟我不一樣的是，它是從第 i 杯往下流 i+1；我的方法是看第 i 杯從 i-1 流

  • 壓縮成 1D array 的作法 Credit

    壓縮成 1D array 的作法
    1
    2
    3
    4
    5
    6
    7
    8
    double champagneTower(int p, int r, int c) {
        double dp[101] = {0.0};
        dp[0] = p;
        for(int row = 1; row <= r; row++)
            for(int i = row; i >= 0; i--)
                dp[i+1] += dp[i] = max(0.0, (dp[i]-1)/2);
        return min(dp[c], 1.0);
    }

心得#

一開始想複雜了，一直想著要一杯一杯模擬，看了題解才突破盲點，可以一次倒完全部