leetcode 1130. 叶值的最小代价生成树

题目描述

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

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

提示：
2 <= arr.length <= 40
1 <= arr[i] <= 15
答案保证是一个 32 位带符号整数，即小于 2³¹。

分析

本题属于哈夫曼树的推广题，不过哈夫曼树要求带权路径和最小，而本题则是要求非叶节点的和最小，非叶节点的值等于其左右子树中最大的叶节点的值之积。可以使用动态规划或者贪心来求解，相对而言，动态规划的思路更容易想到。

动态规划

这题可以用DP求解得益于“数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应”这个条件，也就是说，我们合并叶节点时候，只能合并相邻的两个叶节点，这就与石子合并问题很类似了，属于区间DP的经典问题。设f[i][k]表示合并区间i到k叶节点能够得到的最小非叶节点和，那么状态转移我们就可以枚举最后一次合并的位置，比如说1 2 3 4，最后一次合并的左边部分可以是1,1 2，1 2 3这三种情况，状态转移方程为f[i][k] = max(f[i][j] + f[j+1][k] + d[i][j]*d[j+1][k])。其中d[[i][j]表示i到j区间叶子节点的最大值，可以提前用二重循环初始化一下。因为是求最小解，状态的初始值都是INF，只有区间长度是1的情况，也就是f[i][i] = 0，表示只有一个叶节点，没有合并自然没有非叶节点，和就是0。
区间DP的解法的代码如下：

class Solution {
public:
    int f[45][45],d[45][45];
    int mctFromLeafValues(vector<int>& arr) {
        int n = arr.size();
        for(int i = 0;i < n;i++){
            int k = arr[i];
            for(int j = i;j < n;j++){
                k = max(k,arr[j]);
                d[i][j] = k;
            }
        }
        memset(f,0x2f,sizeof f);
        for(int i = 0;i < n;i++)    f[i][i] = 0;
        for(int len = 2;len <= n;len++){
            for(int i = 0;i + len -1 < n;i++){
                int k = i + len - 1;
                for(int j = i;j < k;j++){
                    f[i][k] = min(f[i][k],f[i][j]+f[j+1][k]+d[i][j]*d[j+1][k]);
                }
            }
        }
        return f[0][n-1];
    }
};

单调栈+贪心

与区间DP求解思路的简洁明了相比，贪心解法的证明和实现都更加的麻烦，实现的麻烦不在于代码的复杂，而是细节容易出错。
对于相邻的三个数abc，我们要么先合并ab，要么先合并bc。先合并ab得到的非叶节点的权值就是ab，然后合并c得到的非叶节点的权值是max(a, b) * c，总的非叶节点权值和S1 = ab + max(a,b) * c；同理，先合并bc得到的非叶节点的权值和S2 = bc + max(b,c) * a，S1和S2这两个式子的值不好比较，我们按照abc三个数的大小分类进行讨论：

• b最大，S1 = ab + bc，S2 = bc + ab，可见b最大时先合并哪边结果都是一样的。
• a最大，S1 = ab + ac，S2 = bc + max(b,c) * a，如果b > c,S2 = b(a + c) < a(b + c) = S1，因为a > b，两个大的乘数之积肯定也更大；如果b < c，S2 = bc + ac < ab + ac = S1，同样是S1更大，这时候先合并右边的和最小。
• c最大，与a最大类似，很容易推出先合并左边的和最小。

通过分类讨论我们可以得出结论，应该先合并较小的两个，在合并较大的两个得到的非叶节点的和更小，也就是像1 2 3 4这种递增序列，我们按顺序合并叶节点即可，对于4 3 2 1这种递减序列，我们倒着合并叶节点即可，对于一般的序列，比如先增后减的序列，像1 2 3 4 3 2，我们可以先合并1 2 3 4，再合并3 2，最后再合并剩下的两部分。

我们可以维护一个单调栈，如果当前元素小于栈顶元素，说明元素是递减的，可以先入栈，后面再进行合并；如果当前元素大于栈顶元素，说明元素是递增的，这时候要视情况去合并了，比如5 3 4，遍历到4时，栈里有5和3两个元素，4 > 3并且4 < 5，这时候可以直接合并3和4；但是像4 3 5这种情况，显然需要先合并3,4；所以栈顶元素需要与次栈顶元素和当前元素中的较小者合并。

元素遍历完之后，如果栈里还有元素，还需要继续合并，栈内元素单调递减，可以从栈顶开始合并。使用单调栈求解可以发现，非叶节点的和等于所有的合并产生的代价之和。我们也不需要可以去求区间内的最大值了，因为当前元素大于栈顶元素时，栈顶元素发生合并后就可以出栈了，而与之合并的更大的元素还在栈中，栈里面始终维护着还需要合并的叶节点中的最大值。
贪心+单调栈解法代码如下：

class Solution {
public:
    int stk[45];
    int mctFromLeafValues(vector<int>& arr) {
        int n = arr.size();
        int tt = -1;
        int res = 0;
        for(int i = 0;i < arr.size();i++) {
            while(tt >= 0 && arr[i] > stk[tt]) {
                if(!tt || stk[tt-1] > arr[i])   res += arr[i] * stk[tt];
                else    res += stk[tt] * stk[tt-1];
                tt--;
            }
            stk[++tt] = arr[i];
        }
        for(int i = tt;i > 0;i--)  res += stk[i] * stk[i-1];
        return res;
    }
};