题目分析

这个题目有一定的难度，首先肯定不能建树。我们要想明白不建树如何求解这个题目。题目的第二个信息非常重要，arr的值是中序遍历的节点值。那么以某个节点为根的叶子节点在数组中就必然是连续的，比如题目中的[6, 2, 4]，那么[6]可以组成一个单独的子树，[2, 4]可以组成一个单独的子树。或者[6, 2]可以组成一个单独的子树，[4]可以组成一个单独的子树。唯独[6, 4]不能组成，因为中间跳跃了2。

动态规划

使用dp[i][j]表示从i索引开始到j索引表示的子树的最小代价生成树。

那么有递推关系

$$ dp[i][j] = min(dp[i][k] + dp[k + 1][j] + maxi[begin][k] * maxi[k + 1][j]) $$

其中maxi[i][j]表示arr[i]到arr[j]的最大值

算法时间复杂度为$O(n^3)$，空间复杂度为$O(n^2)$。

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX)), maxi(n, vector<int>(n, 0));
        for (int num = 1; num <= n; num++) {
            for (int begin = 0; begin < n - num + 1; begin++) {
                if (num == 1) {
                    maxi[begin][begin] = arr[begin];
                    dp[begin][begin] = 0;
                } else {
                    int end = begin + num - 1;
                    maxi[begin][end] = max(maxi[begin][end - 1], arr[end]);
                    for (int mid = begin; mid < end; mid++) {
                        dp[begin][end] = min(dp[begin][end], dp[begin][mid] + dp[mid + 1][end] + maxi[begin][mid] * maxi[mid + 1][end]);
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
};

单调栈

单调栈算法是参考官方题解的思路，我们先发现了第一个叶子节点，然后发现了第二个叶子节点。此时有两种做法，一个是合并，1和2先合并。第二个是先不合并，2可能先和后面的合并结果更小。

如果中间的元素小于两边的元素，此时有两种情况。假设中间的索引为k

arr[k - 1] > arr[k + 1]，那么先合并arr[k]和arr[k + 1]是更好的选择。
arr[k - 1] <= arr[k + 1]，那么先合并arr[k]和arr[k - 1]是更好的选择。

我们以第一种情况进行解释，先合并arr[k]和arr[k + 1]会生成一个值为arr[k] x arr[k + 1]的非叶子节点，因此结果会增加arr[k] x arr[k + 1]，如果合并arr[k]和arr[k - 1]结果会增加arr[k] x arr[k - 1]。因为先合并arr[k]和arr[k + 1]，此时再与arr[k - 1]合并时，结果是arr[k - 1] x arr[k + 1]，因为arr[k + 1]大于arr[k]。先合并arr[k]和arr[k - 1]，此时再与arr[k + 1]合并时，结果是arr[k - 1] x arr[k + 1]。第二次合并相同。因为arr[k - 1] > arr[k + 1]，所以第一次先合并arr[k]和arr[k + 1]更好。

那么可以看出维护一个递减的栈，如果发现元素增加，则说明当前栈顶是一个局部最小值。此时需要进行合并。

算法的时间复杂度为$O(n)$，空间复杂度为$O(n)$。

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        stack<int> s;
        int res = 0;
        for (int x : arr) {
            while (!s.empty() && s.top() <= x) {
                int top = s.top();
                s.pop();
                if (s.empty() || s.top() > x) {
                    res += top * x;
                } else {
                    res += s.top() * top;
                }
            }
            s.push(x);
        }
        while (s.size() >= 2) {
            int top = s.top();
            s.pop();
            res += s.top() * top;
        }
        return res;
    }
};

刷题总结

本题的DP算法是要求同学们一定要掌握的，对于单调栈算法我们做为提高，能掌握最好。