题目描述

给定一个整数数组 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^31）。

算法1

(动态规划) $O(n^3)$

1. f(i, j) 表示构造区间 [i, j] 的最小代价。maxr(i, j) 表示区间 [i, j] 的最大值。
2. 初始时 f(i, j) = INT_MAX，f(i, i) = 0。
3. 转移时，对于 f(i, j)，枚举一个 k 满足 i <= k < j，则 f(i, j) = min(f(i, j), maxr(i, k) * maxr(k + 1, j) + f(i, k) + f(k + 1, j)。
4. 最终答案为 f(0, n - 1)。

时间复杂度

• 状态数为 $O(n^2)$ 个，需要枚举 $O(n)$ 个转移，故时间复杂度为 $O(n^3)$。

空间复杂度

• f 和 maxr 数组需要 $O(n^2)$ 的空间。

C++ 代码

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> f(n, vector<int>(n, INT_MAX));
        vector<vector<int>> maxr(n, vector<int>(n, 0));

        for (int i = 0; i < n; i++) {
            f[i][i] = 0;
            maxr[i][i] = arr[i];
        }

        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++) 
                    f[i][j] = min(f[i][j], maxr[i][k] * maxr[k + 1][j] + f[i][k] + f[k + 1][j]);

                for (int k = i; k <= j; k++)
                    maxr[i][j] = max(maxr[i][j], arr[k]);
            }

        return f[0][n - 1];
    }
};