Minimum Cost Tree From Leaf Values
Given an array arr of positive integers, consider all binary trees such that:
- Each node has either
0or2children. - The values of
arrcorrespond to the values of each leaf in an in-order traversal of the tree. - The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree, respectively.
Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.
Examples
Input: [6,2,4]
Output: 32
Input: [4,11]
Output: 44
Hints
The problem can be approached using dynamic programming where `dp[i][j]` represents the minimum sum of non-leaf nodes for the subarray `arr[i..j]`.
To compute `dp[i][j]`, consider all possible ways to split the subarray into left and right parts (i.e., `k` from `i` to `j-1`), and calculate the product of the maximum leaf values in the left and right parts, then add the results of the left and right subproblems.
The key insight is that the maximum leaf value in any subarray `arr[i..j]` can be precomputed and stored in a separate table `max_val[i][j]` to avoid redundant calculations during the DP process.
Related Problems
Minimum Cost Tree From Leaf Values
Given an array `arr` of positive integers, consider all binary trees such that: