Problem statement

https://binarysearch.com/problems/Minimum-Tree-From-Leaves/

Solution

Equal to Leetcode 1130. Minimum Cost Tree From Leaf Values, just return sum of all values here.

Complexity

It is O(n^3) for time and O(n^2) for space.

Code

class Solution:
    def solve(self, arr):
        n = len(arr)
        m = {(i, j): max(arr[i:j+1]) for i in range(n) for j in range(i, n)}
        
        @lru_cache(None)
        def dp(i, j):
            if i == j: return arr[i]
            return min(dp(i, k) + dp(k + 1, j) + m[i, k]*m[k+1, j] for k in range(i, j))
            
        return dp(0, n - 1)

Remark

There is also O(n) time complexity solution, using monotonic deque.