树形DP or 单调栈贪心：叶值的最小代价生成树

痛定思痛。 2023-10-06 14:02 23阅读 0赞

## 树形DP or 单调栈贪心：叶值的最小代价生成树 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20200731092947298.png]

#### 思路： ####

###### 树形DP： ######

对于题中所给数组，由于数组中的值与中序遍历中叶节点的值对应，则可将数组分为两部分，左部分为左子树叶节点，右部分为右子树叶节点，则根节点的值即为左右两部分数组中最大值的乘积，树中非叶节点和即为根节点的值+左子树非叶节点和+右子树非叶节点和，由于数组的划分是不确定的，因此需找到使得非叶节点和最小的划分

设DP\[i\]\[j\]表示在原数组中左右界分别为i,j的数组得到的树的最小非叶节点和  
M\[i\]\[j\]表示在原数组中左右界分别为i,j的数组中的最大元素值  
![在这里插入图片描述][20200731094041275.png]  
M初值为0，DP\[i\]\[i\]=0表示树中仅有根节点，非叶节点和为0，其余DP的初值为+INF

DP的递推顺序为从最后一个元素向前递推，因为最后需求得的元素是DP\[0\]\[n-1\]，是从后往前推得到的

###### 单调栈贪心： ######

这道题可以看做如下过程：在数组 arr 中，每次取相邻的两个数 a 和 b，然后去掉其中较小的一个，花费代价为 a \* b，求最终将数组消减为一个元素的最小代价。那么，要想获得最小代价，我们应该采取的策略是：对于数组中的某一个数 a，分别向左和向右查询比它大的第一个数（为什么不是选择比它大的数中最小的数，因为需要满足中序遍历的顺序），在这两个数中选择较小的那个数进行组合并消去a，花费的代价最小。这个过程我们可以用单调栈来一次遍历解决掉。

维持一个单调栈，遍历数组元素，栈非空时，当遇到比栈顶元素大的元素，栈顶元素出栈，比较新的栈顶与当前遍历到的元素值，选择较小的一个组合，不断进行此操作直至栈顶元素值大于当前遍历到的元素值或栈为空。最后将当前元素入栈。

最后栈中元素个数若>=2（栈中元素为空或等于1表明已消减完成），说明在遍历的最后出现了连续递减的序列，此时不断将栈顶元素出栈并与新栈顶组合即可

#### 代码： ####

###### 树形DP： ######

class Solution {
        
    public:
        int mctFromLeafValues(vector<int>& arr) {
        
            int n=arr.size();
            int DP[n][n];
            int M[n][n];
            memset( DP,1e+04,sizeof(DP) );
            memset( M,0,sizeof(M) );
            int i;
            int j;
            int k;
            int maxx;
            for( i=0;i<n;i++ )
            {
        
                maxx=0;
                for( j=i;j<n;j++ )
                {
        
                    maxx=max( arr[j],maxx );
                    M[i][j]=maxx;
                }
            }
            for( i=n-1;i>=0;i-- )
                for( j=i;j<n;j++ )
                {
        
                    if( j==i )
                    {
        
                        DP[i][j]=0;
                        continue;
                    }
                    for( k=i;k<=j-1;k++ )
                    {
        
                       DP[i][j]=min( DP[i][j],M[i][k]*M[k+1][j]+DP[i][k]+DP[k+1][j] );
                    }
                }
            return DP[0][n-1];
        }
    };

###### 单调栈贪心： ######

class Solution {
        
    public:
        int mctFromLeafValues(vector<int>& arr) {
        
            stack<int> s;
            int ans=0;
            for( auto x:arr )
            {
        
                while( !s.empty() && s.top()<x )
                {
        
                    int temp=s.top();
                    s.pop();
                    ans+=temp*min( s.empty()? 100:s.top(),x );
                }
                s.push( x );
            }
            while( s.size()>=2 )
            {
        
                int temp=s.top();
                s.pop();
                ans+=temp*s.top();
            }
            return ans;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200731092938624.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[20200731092947298.png]: https://img-blog.csdnimg.cn/20200731092947298.png
[20200731094041275.png]: https://img-blog.csdnimg.cn/20200731094041275.png