DP應用題 香檳塔 Champagne Tower Leetcode #799

這題的題目在這裡:

題目會給定我們一個三角形排列的香檳塔，第一層有一杯酒杯，第二層有兩杯酒杯，...，第k層有k杯酒杯，依此類推。

假如上一層的酒杯已經倒滿杯，多出來的部分會向下一層流動，並且均分一半給下一層最靠近的兩杯酒杯。

題目問，假如一開始在最上層第一杯開始注入香檳，初始量為參數poured
，最後第i層的第j杯會有多少香檳在裡面?

測試範例:

Example 1:

Input: poured = 1, query_row = 1, query_glass = 1
Output: 0.00000
Explanation: We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.

Example 2:

Input: poured = 2, query_row = 1, query_glass = 1
Output: 0.50000
Explanation: We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.

Example 3:

Input: poured = 100000009, query_row = 33, query_glass = 17
Output: 1.00000

約束條件:

Constraints:

• 0 <= poured <= 109
• 0 <= query_glass <= query_row < 100

演算法:

關鍵在於找出香檳酒流動的共同模式(common pattern)

令champagne[row][col] 為指定座標[row][col]這杯酒杯所擁有的香檳酒量。

都下這一層 champagne[row][col] 這個酒杯假如滿杯，
滿杯代表champagne[row][col] > 1，

多出來的部分，會均分對半分給下一層。
多出來的部分 = champagne[row][col] - 1

多出來的部分 * 1/2 = (champagne[row][col] - 1) / 2
就是下一層最靠近的那兩杯
champagne[row+1][col]和champagne[row+1][col+1]
所獲得的酒量。

再往下，同樣依循共同的模式去計算酒的存量和溢出量。
最後返回指定那一杯的酒量，就是答案。

程式碼:

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        
        # Volume of champagne in champagneTower at [row][col]
        champagne = [ [ 0 for _ in range(row) ] for row in range(1, 102)]

        # Top level [0][0] is initialized with poured champagne
        champagne[0][0] = poured

        # From top level to bottom level
        for row in range(query_row+1):

            # From leftmost glass to rightmist glass
            for col in range(row+1):

                # If current glass has more than one cup of champagne, 
                # then overflowing part is flowing to nearest two glass on next level
                if champagne[row][col] > 1:

                    # nearest glass on next level on left hand side
                    champagne[row+1][col] += ( champagne[row][col] - 1 ) / 2

                    # nearest glass on next level on right hand side
                    champagne[row+1][col+1] += ( champagne[row][col] - 1 ) / 2
        
        # Remember that each glass can take "at most" one cup of champagne
        return min( champagne[query_row][query_glass], 1 )

時間複雜度:

O(n^2)
外層迴圈耗費O(n)，內層迴圈也耗費O(n)

空間複雜度:

O( n^2 ) DP table是一個三角形形狀的二維陣列。

空間優化的版本:
其實我們只需要儲存當下最靠近的這兩層酒杯的酒量即可。

class Solution:
　def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
　　
　　# Volume of champagne in champagneTower at [row][col]
　　# Top level [0][0] is initialized with poured champagne
　　champagne = [poured]

　　# From top level to bottom level
　　for row in range(query_row):
　　　
　　　next_level_champagne = [ 0 for _ in range( len(champagne) + 1 ) ]
　　　# From leftmost glass to rightmist glass
　　　for col in range(row+1):

　　　　# If current glass has more than one cup of champagne, 
　　　　# then overflowing part is flowing to nearest two glass on next level
　　　　if champagne[col] > 1:

　　　　　# nearest glass on next level on left hand side
　　　　　next_level_champagne[col] += ( champagne[col] - 1 ) / 2

　　　　　# nearest glass on next level on right hand side
　　　　　next_level_champagne[col+1] += ( champagne[col] - 1 ) / 2

　　　# update champagne tower from top to bottom
　　　champagne = next_level_champagne

　　# Remember that each glass can take "at most" one cup of champagne
　　return min( champagne[query_glass], 1 )

時間複雜度:

O(n^2)
外層迴圈耗費O(n)，內層迴圈也耗費O(n)

空間複雜度:

O( n ) DP table是兩個一維陣列，O(n) + O(n)在數量級上還是O(n)。

Reference:

[1] Python simulation in 2D DP [w/ Visualization] - Champagne Tower - LeetCode