Posted on 2023-09-24 16:53
Uriel 閱讀(59)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
數學 、
閑來無事重切Leet Code
有query_row層壘起來的玻璃杯，第i層有i個杯子，從第一層開始倒水，倒進去poured杯水，求問第query_row層第query_glass個杯子有多少水
按層往下算，每次減去當前杯子裝進的1杯，剩下對半分入下一層相鄰兩個杯子
1 #799
2 #Runtime: 59 ms (Beats 62.50%)
3 #Memory: 13.3 MB (Beats 45.11%)
4
5 class Solution(object):
6 def champagneTower(self, poured, query_row, query_glass):
7 """
8 :type poured: int
9 :type query_row: int
10 :type query_glass: int
11 :rtype: float
12 """
13 dp = [[0 for _ in range(x)] for x in range(1, query_row + 2)]
14 dp[0][0] = poured
15 for i in range(query_row):
16 for j in range(len(dp[i])):
17 tp = (dp[i][j] - 1) / 2.0
18 if tp > 0:
19 dp[i + 1][j] += tp
20 dp[i + 1][j + 1] += tp
21 return dp[query_row][query_glass] if dp[query_row][query_glass] <= 1 else 1