本題為11月20日力扣每日一題
題目來源:力扣第799題
題目tag:動態規劃 模擬
題面
我們把玻璃杯擺成金字塔的形狀，其中第一層有1個玻璃杯，第二層有2個，依次類推到第100層，每個玻璃杯(250ml)將盛有香檳，
從頂層的第一個玻璃杯開始傾倒一些香檳，當頂層的杯子滿了，任何溢位的香檳都會立刻等流量的流向左右兩側的玻璃杯，當左右兩邊的杯子也滿了，就會等流量的流向它們左右兩邊的杯子，依次類推，（當最底層的玻璃杯滿了，香檳會流到地板上）
例如，在傾倒一杯香檳后，最頂層的玻璃杯滿了，傾倒了兩杯香檳后，第二層的兩個玻璃杯各自盛放一半的香檳，在倒三杯香檳后，第二層的香檳滿了 - 此時總共有三個滿的玻璃杯，在倒第四杯后，第三層中間的玻璃杯盛放了一半的香檳，他兩邊的玻璃杯各自盛放了四分之一的香檳，如下圖所示，
現在當傾倒了非負整數杯香檳后，回傳第i行j個玻璃杯所盛放的香檳占玻璃杯容積的比例（i和j都從0開始），
示例
示例 1:
輸入:
poured(傾倒香檳總杯數) = 1, query_glass(杯子的位置數) = 1, query_row(行數) = 1
輸出:
0.00000
解釋:
我們在頂層（下標是（0，0））倒了一杯香檳后，沒有溢位，因此所有在頂層以下的玻璃杯都是空的，
示例 2:
輸入: poured(傾倒香檳總杯數) = 2, query_glass(杯子的位置數) = 1, query_row(行數) = 1
輸出: 0.50000
解釋: 我們在頂層（下標是（0，0）倒了兩杯香檳后，有一杯量的香檳將從頂層溢位，位于（1，0）的玻璃杯和（1，1）的玻璃杯平分了這一杯香檳，所以每個玻璃杯有一半的香檳，
示例 3:
輸入: poured = 100000009, query_row = 33, query_glass = 17
輸出: 1.00000
提示
0 <= poured <= 109
0 <= query_glass <= query_row < 100
思路分析
這題的tag標的是動態規劃,其實直接進行模擬也可.
我們完全可以假設一開始所有香檳都倒到了最頂上的杯子上,然后我們挨個處理每個杯子,把溢位的香檳分別倒到下面的兩個杯子中,最后看看目標杯子里有多少香檳即可.
如果一定要從動態規劃的角度來理解的話,我們可以把每一個杯子都看成是一個小"杯子三角形"最頂上的杯子.每次溢位的香檳,可以看成是往其下面的兩個小"杯子三角形"倒的香檳.根據這個思路可以寫出一個遞回形式的代碼.顯然可以直接借助一個陣列代替這個遞回,改成迭代形式,這時的代碼與直接模擬寫出來的代碼是一致的.
參考代碼
class Solution
{
public:
double champagneTower(int poured, int query_row, int query_glass)
{
vector<vector<double>> glasses(100, vector<double>(100, 0));
glasses[0][0] = poured; // 初始狀態,把香檳全部倒進第一個杯子
for (int i = 0; i < query_row; i++) // 模擬到目標行就好了
{
for (int j = 0; j <= i; j++)
{
if (glasses[i][j] >= 1)
{
if (i + 1 < 100) // 如果底下還有一層杯子
{
glasses[i + 1][j] += (glasses[i][j] - 1) / 2.0; // 溢位的一半到下一個杯子
glasses[i + 1][j + 1] += (glasses[i][j] - 1) / 2.0; // 溢位的一半到下一個杯子
}
glasses[i][j] = 1; // 溢位剩下就是滿(底下沒有杯子時溢位的在地板上)
}
}
}
return glasses[query_row][query_glass] >= 1 ? 1 : glasses[query_row][query_glass]; // 如果溢位就是滿,否則多少就是多少
}
};
"正是我們每天反復做的事情，最終造就了我們，優秀不是一種行為，而是一種習慣" ---亞里士多德
這里是浙江理工大學22屆ACM集訓隊的成員一枚鴨!
本文首發于博客園，作者：星雙子，除了我自己的轉載請注明原文鏈接：https://www.cnblogs.com/geministar/p/LeetCode799.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/536895.html
標籤：其他