23.08.05 Today’s Leetcode

95. Unique Binary Search Trees II

DFS Approach

class Solution:
    def generateTrees(self, n: int, k=1) -> List[Optional[TreeNode]]:
        if n < k: 
            return [None]
        tree_list = [TreeNode(i, left, right) 
                     for i in range(k, n + 1) 
                     for left in self.generateTrees(i - 1, k) 
                     for right in self.generateTrees(n, i + 1)]
        return tree_list

799. Champagne Tower

DP Approach

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        dp = [0] * (query_row + 1)
        dp[0] = poured

        def help(cur):
            arr = [0] * (query_row + 1)
            for i in range(query_row):
                if cur[i] < 1:
                    continue
                temp = (cur[i] - 1) / 2
                arr[i] += temp
                arr[i + 1] += temp
            return arr

        for i in range(query_row):
            print(dp)
            dp = help(dp)
        
        return min(1, dp[query_glass])