→ wwndbk: 大師 09/24 16:58
→ Rushia: 我看別人都用模擬的 我又想iwin了 09/24 17:00
https://leetcode.com/problems/champagne-tower/description
799. Champagne Tower
有一個香檳塔，第0層有一個杯子，第1層有兩個杯子（編號為0和1），以此類推，共有
100層杯子。
每個杯子可以裝1個單位的香檳，超出的部分會均勻的往下一層流，若我們往
香檳塔的頂部倒入poured單位的香檳，求出第query_row層的編號為query_glass的
杯子裡面有多少香檳。
https://s3-lc-upload.s3.amazonaws.com/uploads/2018/03/09/tower.png
Example：
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.
思路：
1.這個問題是一個遞迴問題，假如 f(i,j) 是第 i 層編號為 j 的杯子流下來的香檳單位
，那麼 f(0,0) = poured，且 f(i,j) = (f(i-1, j)-1)/2 + (f(i-1, j-1)-1)/2。
(如果f(i,j)-1 < 0 取0)
2.有遞迴關係式之後就可以直接套遞迴求解了，但是遞迴過程中有需多重複計算，所以
我們可以對函數作 memoization 記錄已經算過的值。
3.因為題目是要求杯子裡的容量，所以我們取 MIN(f(i,j), 1) 即可。
Java Code：
-----------------------------------------
class Solution {
private Double[][] memo;
public double champagneTower(int poured, int query_row, int query_glass) {
if (poured == 0) return 0;
memo = new Double[query_row + 1][];
for (int i = 0; i < memo.length; i++) {
memo[i] = new Double[query_glass + 1];
}
memo[0][0] = (double)poured;
return Math.min(dfs(query_row, query_glass), 1);
}
private double dfs(int curr_row, int curr_glass) {
if (curr_row < 0 || curr_glass < 0) {
return 0;
}
if (memo[curr_row][curr_glass] != null) {
return memo[curr_row][curr_glass];
}
return memo[curr_row][curr_glass] = (Math.max(0, dfs(curr_row - 1,
curr_glass - 1) - 1))/2
+ (Math.max(0, dfs(curr_row - 1, curr_glass) - 1))/2;
}
}
-----------------------------------------
姆咪==
--
https://i.imgur.com/3e5CZfj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1695545720.A.6C6.html
※ 編輯: Rushia (122.100.73.13 臺灣), 09/24/2023 16:56:18