leetcode1130

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

        def dp(i, j):
            if i == j:
                return 0
            if a[i][j] != 0:
                return a[i][j]
            res = float('inf')
            for k in range(i, j):
                res = min(res, dp(i, k) + dp(k + 1, j) + max(arr[i:k + 1]) * max(arr[k + 1:j + 1]))
            a[i][j] = res
            return res

        return dp(0, len(arr) - 1)