799. Champagne Tower

link

The key here is not think about the every step or how it flows.

Think about the final status, so from the top, if one glasses get more than 1, then it will spilt into two side.

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:

        current = 0

        dp = [float(poured)]

        # if query_row == 0:
        #     return  min(1, dp[0])

        while current != query_row:

            dp_next = [0] * (current + 2)

            for i in range(len(dp)):
                if dp[i] <= 1:
                    continue
                dp[i] -= 1
                dp_next[i] += dp[i] / 2
                dp_next[i+1] += dp[i] / 2


            dp = dp_next
                
            current += 1

        return min(1,dp[query_glass])