leetcode 1130. Minimum cost spanning tree of leaf value

Title Description

Here's an array of positive integers arr, Consider all binary trees that meet the following conditions ：
Every node has 0 One or 2 Child node .
Array arr The value in the tree corresponds to the value of each leaf node in the middle order traversal one by one .（ Knowledge review ： If a node has 0 Child node , So this node is a leaf node .）
The value of each non leaf node is equal to the product of the maximum value of nodes in its left and right subtrees .
In all such binary trees , Returns the minimum possible sum of the values for each non leaf node . This sum is worth one 32 An integer .
Example ：
Input ：arr = [6,2,4]
Output ：32
explain ：
There are two possible trees , The sum of the non leaf nodes of the first kind is 36, The sum of the second non leaf nodes is 32.

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

Tips ：
2 <= arr.length <= 40
1 <= arr[i] <= 15
The answer is guaranteed to be 32 Bit signed integer , That is less than 2³¹.

analysis

This problem belongs to the generalization of Huffman tree , However, Huffman tree requires weighted path and minimum , This problem requires the minimum sum of non leaf nodes , The value of a non leaf node is equal to the product of the values of the largest leaf node in its left and right subtrees . Dynamic programming or greed can be used to solve , Relatively speaking , The idea of dynamic planning is easier to think of .

Dynamic programming

This question can be used DP Solution benefits from “ Array arr The value in the tree corresponds to the value of each leaf node in the middle order traversal one by one ” This condition , in other words , When we merge leaf nodes , Only two adjacent leaf nodes can be merged , This is very similar to the stone merging problem , It belongs to the interval DP The classic question of . set up f[i][k] Represents the merging interval i To k The minimum non leaf nodes and that leaf nodes can get , Then we can enumerate the location of the last merge , for instance 1 2 3 4, The left part of the last merge can be 1,1 2,1 2 3 These three situations , The equation of state transfer is f[i][k] = max(f[i][j] + f[j+1][k] + d[i][j]*d[j+1][k]). among d[[i][j] Express i To j The maximum value of an interval leaf node , You can initialize it with a double loop in advance . Because it is to find the minimum solution , The initial values of states are INF, Only the interval length is 1 The situation of , That is to say f[i][i] = 0, Indicates that there is only one leaf node , There are no non leaf nodes without merging , And is 0.
Section DP The code of the solution is as follows ：

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];
    }
};

Monotonic stack + greedy

And interval DP The simplicity of the solution is compared with , The proof and implementation of greedy solution are more troublesome , The trouble with implementation is not the complexity of the code , But the details are easy to make mistakes .
For three adjacent numbers abc, We can either merge first ab, Or merge first bc. Merge first ab The weight of the non leaf node obtained is ab, Then merge c The weight of the non leaf node obtained is max(a, b) * c, Sum of total non leaf node weights S1 = ab + max(a,b) * c; Empathy , Merge first bc The sum of the weights of the non leaf nodes S2 = bc + max(b,c) * a,S1 and S2 The values of these two formulas are not easy to compare , We are in accordance with the abc The size classification of three numbers is discussed ：

• b Maximum ,S1 = ab + bc,S2 = bc + ab, so b At the maximum, the result of which side is merged first is the same .
• a Maximum ,S1 = ab + ac,S2 = bc + max(b,c) * a, If b > c,S2 = b(a + c) < a(b + c) = S1, because a > b, The product of two large multipliers must also be larger ; If b < c,S2 = bc + ac < ab + ac = S1, The same is S1 Bigger , At this time, the sum on the right is merged first .
• c Maximum , And a Maximum similarity , It's easy to roll out to merge the left and the smallest first .

Through classified discussion, we can draw a conclusion , The smaller two should be merged first , The sum of the non leaf nodes obtained by merging the larger two is smaller , It's like 1 2 3 4 This increasing sequence , We can merge the leaf nodes in order , about 4 3 2 1 This decreasing sequence , We can merge leaf nodes in reverse , For general sequences , For example, the sequence of increasing first and then decreasing , image 1 2 3 4 3 2, We can merge first 1 2 3 4, Re merger 3 2, Finally, merge the remaining two parts .

We can maintain a monotone stack , If the current element is smaller than the top of the stack , Indicates that the element is decreasing , You can put it on the stack first , Merge later ; If the current element is larger than the top of the stack , Indicates that the element is incremented , At this time, it is necessary to merge according to the situation , such as 5 3 4, Traversing 4 when , In the stack 5 and 3 Two elements ,4 > 3 also 4 < 5, At this time, you can merge directly 3 and 4; But like 4 3 5 This situation , Obviously we need to merge first 3,4; Therefore, the stack top element needs to be merged with the smaller of the secondary stack top element and the current element .

After element traversal , If there are elements in the stack , You need to continue merging , The elements in the stack decrease monotonically , You can merge from the top of the stack . Using monotone stack solution, we can find , The sum of non leaf nodes is equal to the sum of all the costs of merging . We don't need to be able to find the maximum value in the interval , Because the current element is larger than the top element of the stack , After the top elements of the stack are merged, they can be pushed out of the stack , The larger elements merged with it are still on the stack , The stack always maintains the maximum value of leaf nodes that need to be merged .
greedy + The monotone stack solution code is as follows ：

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;
    }
};