LeetCode 799. 香檳塔（DP動態規劃）

1. 題目

我們把玻璃杯擺成金字塔的形狀，其中第一層有1個玻璃杯，第二層有2個，依次類推到第100層，每個玻璃杯(250ml)將盛有香檳。

從頂層的第一個玻璃杯開始傾倒一些香檳，當頂層的杯子滿了，任何溢位的香檳都會立刻等流量的流向左右兩側的玻璃杯。
當左右兩邊的杯子也滿了，就會等流量的流向它們左右兩邊的杯子，依次類推。（當最底層的玻璃杯滿了，香檳會流到地板上）

例如，在傾倒一杯香檳後，最頂層的玻璃杯滿了。傾倒了兩杯香檳後，第二層的兩個玻璃杯各自盛放一半的香檳。在倒三杯香檳後，第二層的香檳滿了 - 此時總共有三個滿的玻璃杯。在倒第四杯後，第三層中間的玻璃杯盛放了一半的香檳，他兩邊的玻璃杯各自盛放了四分之一的香檳，如下圖所示。

現在當傾倒了非負整數杯香檳後，返回第 i 行 j 個玻璃杯所盛放的香檳佔玻璃杯容積的比例（i 和 j都從0開始）。

範例 1:
輸入: poured(傾倒香檳總杯數) = 1, 
query_glass(杯子的位置數) = 1, 
query_row(行數) = 1
輸出: 0.0
解釋: 我們在頂層（下標是（0，0））倒了一杯香檳後，
沒有溢位，因此所有在頂層以下的玻璃杯都是空的。

範例 2:
輸入: poured(傾倒香檳總杯數) = 2, 
query_glass(杯子的位置數) = 1, 
query_row(行數) = 1
輸出: 0.5
解釋: 我們在頂層（下標是（0，0）倒了兩杯香檳後，
有一杯量的香檳將從頂層溢位，
位於（1，0）的玻璃杯和（1，1）的玻璃杯平分了這一杯香檳，
所以每個玻璃杯有一半的香檳。

注意:
poured 的範圍[0, 10 ^ 9]。
query_glass 和query_row 的範圍 [0, 99]。

來源：力扣（LeetCode） 連結：https://leetcode-cn.com/problems/champagne-tower
著作權歸領釦網路所有。商業轉載請聯絡官方授權，非商業轉載請註明出處。

2. 解題

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
    	vector<vector<double>> dp(101, vector<double>(101, 0.0));
    	double up_l, up_r;
    	dp[0][0] = poured;
    	for(int i = 1; i <= query_row; ++i) 
    	{
    		for(int j = 0; j <= i; ++j)
    		{
    			up_l = j > 0 ? dp[i-1][j-1] : 0;//上層左側酒量
    			up_r = dp[i-1][j];//上層右側酒量
    			dp[i][j] += up_l > 1 ? (up_l-1)/2.0 : 0;
    			//自己需要留下一杯 -1， 不夠的話得到 0
    			dp[i][j] += up_r > 1 ? (up_r-1)/2.0 : 0;
    			//自己需要留下一杯 -1， 不夠的話得到 0
    		}
    	}
    	return min(1.0, dp[query_row][query_glass]);
    }
};

24 ms 41.6 MB

祝大家國慶節中秋節快樂！

---

我的CSDN部落格地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！