文章目錄
- 1. 題目
- 2. 解題
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阿明），一起加油、一起學習進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/148949.html
標籤：其他
上一篇：IDEA視窗最小化不顯示解決方案