leetcode 1130

问题

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:

1
2
3
4
5
6
7
8
9
10
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).

分析

思路1: 使用区间DP，假设$f(i,j)$ 表示在区间 $[i, j]$ 上的子问题的解，那么有转台转移方程如下：
$$
f(i,j) = \min \limits_{i\leq k <j} \{f(i,k)+f(k+1,j)+max\{a[i..k]\}*max\{a[k+1 … j]\}\}
$$
目标：$f(0,n-1)$。时间复杂度，$O(n^3)$，空间复杂度，$O(n^2)$。

思路2: 我们来重新理解一下这道题目，自底向上考虑，现在给你一个数组 arr[] = {x1, x2, x3,...,xn} ，初始时，每个元素充当一个只有根节点的子树，然后两两相邻的子树会发生碰撞合并，合并的代价为两个子树分别的最大值相乘，这里我们可以看出两颗子树合并之后，只有子树的最大值对后续的结果产生影响，其他的值可以认为是从数组中删除掉了。于是题目可以改写为如下描述：

给定一个数组arr，其中每两个相邻的元素 a 和 b 可以发生碰撞然后消除a和b中较小的那个元素，代价为 a*b，剩余元素可以继续执行上述消除操作，直到数组最终仅剩下一个元素。求所消耗的总代价最小是多少？

可以看出 arr 除了最大的那个元素之外，其他所有元素都难以逃脱被消除的命运，因此我们只确定出arr中除了那个最大的元素，其余每个元素被消除时所需要的最小代价即可。

假设当前数组arr中的最小元素是x，其左边元素为left，右边元素为right。我们首先可以做确定的就是这个最小值x，因为它不可能去消除别人，纯天然无公害。消掉x所需要的代价就是 min(left, right)*x ，可以证明如果不是被left或者right消掉的话，那么在消掉x的时候，left或者right肯定已经有一个被消掉了，那么所需要的代价就大于 min(left, right)*x 了。

这样我们每次可以找到当前数组中的最小值，然后计算出其代价累加到最终的结果中，直到数组的长度为1为止。

思路3: 在思路2的基础上，分析可知，每个元素被消除的代价就是其左边最近一个大于等于它的元素和右边一个最近大于等于它的元素中最小的一个乘以它自身。因此，我们可以维护一个单调递减的栈，每当有元素出栈时，就可以根据该出栈元素，出栈后的栈顶元素以及待入栈元素确定该出栈元素被消除时所需要的代价。完成数组的遍历之后，栈中的元素都没有右边的最大值，在栈的位置中其下方的元素，就是其左边最近的一个比它大的元素。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 区间DP
class Solution {
public:
    int mctFromLeafValues(vector<int>& a) {
        int n = a.size();
        vector<vector<int>> maxVal(n, vector<int>(n, 0));
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
        for (int i = 0; i < n; ++i) {
            maxVal[i][i] = a[i];
            for (int j = i+1; j < n; ++j) {
                maxVal[i][j] = max(maxVal[i][j-1], a[j]);
            }
        }
        
        for (int i = 0; i < n; ++i)
            dp[i][i] = 0;
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i < n-len+1; ++i) {
                int j = i+len-1;
                for (int k = i; k < j; ++k) {
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+maxVal[i][k]*maxVal[k+1][j]);
                }
            }
        }
        return dp[0][n-1];
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 思路2，没有用栈
class Solution {
public:
    list<int>::iterator findLargestOne(list<int> &l) {
        auto ans = l.begin();
        for (auto it = l.begin(); it != l.end(); ++it) {
            if (*it < *ans)
                ans = it;
        }
        return ans;
    }
    int mctFromLeafValues(vector<int>& arr) {
        list<int> l(arr.begin(), arr.end());
        int ret = 0;
        while (l.size() > 1) {
            auto it = findLargestOne(l);
            auto left  = it;
            auto right = it;
            if (left == l.begin()) left = l.end();
            else                   left--;
            right++;
            ret += *it * min(left==l.end()? INT_MAX: *left, 
                          right==l.end()? INT_MAX: *right);
            l.erase(it);
        }
        return ret;
    }
};

代码3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 单调栈 O(n)
class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        int ans = 0;
        stack<int> s;
        s.push(INT_MAX);
        for (int a: arr) {
            while (a >= s.top()) {
                int x = s.top();
                s.pop();
                ans += x*min(s.top(), a);
            }
            s.push(a);
        }
        while (s.size() > 2) {
            int x = s.top();
            s.pop();
            ans += x*s.top();
        }
        return ans;
    }
};