Leetcode 1228 Solution

This article provides solution to leetcode question 1228 (minimum-cost-tree-from-leaf-values)
Categories:
Tags:
Access this page by simply typing in "lcs 1228" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/minimum-cost-tree-from-leaf-values

Solution

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        dp = [[0] * len(arr) for _ in range(len(arr))]

        for i in range(len(arr) - 1, -1, -1):
            for j in range(i, len(arr)):
                if i == j:
                    continue

                left_max = [0] * (j - i + 1)
                right_max = [0] * (j - i + 1)

                curr_max = 0
                for k in range(len(left_max)):
                    curr_max = max(curr_max, arr[k + i])
                    left_max[k] = curr_max

                curr_max = 0
                for k in reversed(range(len(left_max))):
                    curr_max = max(curr_max, arr[k + i])
                    right_max[k] = curr_max

                opt = sys.maxsize
                for k in range(i, j):
                    opt = min(opt, dp[i][k] + dp[k + 1][j] + left_max[k - i] * right_max[k - i + 1])
                dp[i][j] = opt

        return dp[0][len(arr) - 1]