1130. Minimum Cost Tree From Leaf Values - cocoder39/coco39_LC GitHub Wiki

1130. Minimum Cost Tree From Leaf Values

Option 1: recursion + cache

N^2 subproblems and O(N) time complexity to solve each subproblem so total time complexity is O(N^3)

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n = len(arr)
        memo = [[0] * n for i in range(n)]
        
        
        def minCostSubTree(left, right):
            if left == right:
                return 0
            
            if memo[left][right] > 0:
                return memo[left][right]
        
            res = float("inf")
            for i in range(left, right):
                left_value = minCostSubTree(left, i)
                right_value = minCostSubTree(i+1, right)
                cur = max(arr[left:i+1]) * max(arr[i+1:right+1])
                res = min(res, cur + left_value + right_value)
            
            memo[left][right] = res
            return res
        
        return minCostSubTree(0, n-1)

Option 2: eliminate the node with min value and the cost to eliminate the node is min_node * min(left_of_min_node, right_of_min_node)

2.1: greedy O(N^2)

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        res = 0
        n = len(arr)
        while len(arr) > 1:
            i = arr.index(min(arr))
            if 0 < i < len(arr) - 1:
                res += min(arr[i-1], arr[i+1]) * arr[i]
            else:
                res += (arr[i+1] if i == 0 else arr[i-1]) * arr[i]
            arr.pop(i)
        return res

2.2: Monotonic stack O(N)

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        stack = []
        res = 0
        for num in arr:
            while stack and num > stack[-1]:
                cur_min = stack.pop()
                neighbor = min(num, stack[-1]) if stack else num
                res += cur_min * neighbor
            stack.append(num)
        
        while len(stack) > 1:
            res += stack.pop() * stack[-1]
        return res