题目描述

Given an array arr of positive integers, consider all binary trees such that:

• Each node has either 0 or 2 children;
• The values of arr correspond to the values of each leaf in an in-order traversal of the tree. (Recall that a node is a leaf if and only if it has 0 children.)
• 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.

Example 1:

Input: arr = [6,2,4]
Output: 32
Explanation:
There are two possible trees.  The first has non-leaf node sum 36, and the second has non-leaf node sum 32.

    24            24
   /  \          /  \
  12   4        6    8
 /  \               / \
6    2             2   4

Constraints:

• 2 <= arr.length <= 40
• 1 <= arr[i] <= 15
• It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).

题意：给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：每个节点都有 0 个或是 2 个子节点。
数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。（知识回顾：如果一个节点有 0 个子节点，那么该节点为叶节点。）每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。

算法1

(动态规划) $O(n^3)$

题解1：$f(i,j)$代表使用$arr[i:j]$构成的树所有非叶子节点的最小值，$max_v(i,j)$代表区间$arr[i:j]$的最大值。考虑每一个将区间分成两部分的可能解，那么状态转移方程如下：

$f(i,j) = min(f(i,k)+f(k+1,j) + max_v(i,k)*max_v(k+1,j)),i\leq k < j$

最后答案就是$f(0,n-1)$

时间复杂度为：$O(n^3)$

C++ 代码

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        vector<vector<int>> max_v(n,vector<int>(n,0));
        for(int i = 0; i < n ; i ++)
            max_v[i][i] = arr[i];
        for(int d = 1 ; d < n ; d ++)
        {
            for(int i = 0 ; i + d < n ; i++)
            {
                int j = i + d;
                max_v[i][j] = max(max_v[i][j - 1],arr[j]);
            }
        }
        for(int i = 0 ; i < n - 1 ; i ++)
            dp[i][i + 1] = arr[i] * arr[i + 1];
        for(int d = 2 ; d < n ; d ++)
        {
            for(int i = 0 ; i + d < n ; i ++)
            {
                int j = i + d;
                int cur_min = INT_MAX;
                for(int k = i ; k < j ; k ++)
                    cur_min = min(cur_min,dp[i][k] + dp[k + 1][j] + max_v[i][k]*max_v[k + 1][j]);
                dp[i][j] = cur_min; 
            }
        }
        return dp[0][n - 1];
    }
};

算法2

(单调栈) $O(n)$

题解2:单调栈。根据题意我们知道，每次两个相邻元素组成一棵子树后，会将较小的元素删去，留下较大的元素。所以我们的目标就是每次删除局部最小的那个元素。比如[6,2,4]中2就是局部最小因为他小于左右两边的元素。我们将局部最小的元素和两边较小的元素相乘加入答案，同时将这个局部最小的元素抹去。如：

[6,2,4,8] res = 0
[6,4,8] res = 8
[6,8] res = 8 + 24
[8] res = 8 + 24 + 48

我们考虑使用一个单调递减栈来存储数组元素，如果当前元素小于等于栈顶元素直接入栈；否则，说明当前栈顶元素是一个局部最小值，我们用这个局部最小值的两端较小与栈顶元素相乘，同时将栈顶元素出栈，重复上述操作，直至栈顶元素不是局部最小值，再将当前元素入栈。处理完整个数组后，如果栈中还有多的元素，我们从栈顶依次往下乘加入答案即可。

这里为了处理边界情况，先在栈中插入了一个INT_MAX。

时间复杂度：每个元素入栈一次，出栈一次。所以总的时间复杂度是$O(n)$。

C++ 代码

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        int n = arr.size(),res = 0;
        stack<int> st;
        st.push(INT_MAX);
        for(int i = 0 ; i < n ; i ++)
        {
            if(st.top() >= arr[i]) 
                st.push(arr[i]);
            else
            {
                while(arr[i] > st.top())
                {
                    int pre = st.top();
                    st.pop();
                    res += pre * min(st.top(),arr[i]);
                }
                st.push(arr[i]);
            }
        }
        while(st.size() > 2)
        {
            int cur = st.top();
            st.pop();
            res += cur * st.top();
        }
        return res;
    }
};