Minimum Cost Tree From Leaf Values

Intuition

This problem could be solved by Dynamic Programming. For each group of numbers from i to j, the minimum cost is:

min([cost[i:mid] + cost[mid:j] + prod[i:mid] * prod[mid:j] for mid in [i, j])

So we could get the overall minumum cost by DB.

Solution


class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        n = len(arr)
        cost = [[-1] * n for _ in range(n)]
        max_leaf = [[-1] * n for _ in range(n)]
        for lo in range(n):
            cost[lo][lo] = arr[lo]
            max_leaf[lo][lo] = arr[lo]

            for hi in range(lo + 1, n):
                max_leaf[lo][hi] = max(max_leaf[lo][hi - 1], arr[hi])

        for length in range(2, n + 1):
            for lo in range(n - length + 1):
                hi = lo + length - 1
                min_cost = float('inf')
                # mid is the start of the second part
                for mid in range(lo + 1, hi + 1):
                    current = max_leaf[lo][mid - 1] * max_leaf[mid][hi]
                    current_cost = cost[lo][mid - 1] + cost[mid][hi] + current
                    min_cost = min(
                            min_cost,
                            current_cost
                        )
                cost[lo][hi] = min_cost
        return cost[0][n - 1] - sum(arr)