Posted on 2023-09-24 16:53
Uriel 阅读(18)
评论(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