Q63 Champagne Tower - LeetCode 799
Sun Apr 02 2023 15:39:09 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public double champagneTower(int poured, int query_row, int query_glass) {
/* Q63 of dp playlist , the tower is nothing but a 2d array , make a 2d dp
of size k+1(to be on safe side) , and simply find spare for each glass
and pass on spare/2 to both glasses below it
travel the dp from left to right
*/
double[][] dp = new double[102][102];
dp[0][0] =(double) poured; //adding water to the first glass
for(int i = 0 ; i <= query_row ; i++){
for(int j = 0 ; j <= i ; j++){
//calculating spare and filling both glasses directly below
//if the current glass has overflow
if(dp[i][j] > 1.0){
double spare = dp[i][j] - 1.0;
dp[i+1][j] += spare / 2.0;
dp[i+1][j+1] += spare / 2.0;
dp[i][j] = 1.0;
}
}
}
return dp[query_row][query_glass];
}
}
content_copyCOPY
https://leetcode.com/problems/champagne-tower/
Comments