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.
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)