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]; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter