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

发表于 分类于 阅读次数： Waline： 本文字数： 837 阅读时长 ≈ 3 分钟

考点

  • 区间DP
  • 单调栈
  • 贪心

思路

一、问题描述（抽象化）

给定一个长度为 \(n\) 的数组 \[ \text{arr} = [a_0, a_1, \dots, a_{n-1}] \] 需要构造一棵满二叉树，满足：

  • 每个叶子结点按从左到右的顺序，依次对应 arr 中的元素；
  • 每个非叶子结点的值等于其左右子树中最大叶子值的乘积；
  • 目标是 最小化所有非叶子结点值之和。

二、问题建模：区间 DP 的视角

1. 关键观察

  • 树的中序遍历叶子顺序固定，即始终是 arr 的顺序；

  • 任意一棵合法的树，本质上是在数组上不断将某个区间 \([i, j]\) 一分为二： \[ [i, k] \quad | \quad [k+1, j] \]

  • 区间 \([i, j]\) 对应一棵子树，其根节点的值只与左右区间的最大叶子值有关。

这使得问题天然适合用 区间 DP 建模。

三、状态定义

定义状态： \[ f[i][j] = \text{使用区间 } [i, j] \text{ 内的叶子构造子树时，非叶子结点值之和的最小值} \]

边界条件

  • 当 \(i = j\) 时，区间中只有一个叶子，没有非叶子结点：

\[ f[i][i] = 0 \]

四、辅助预处理：区间最大值

在状态转移中会频繁用到： \[ \max(\text{arr}[i..j]) \] 因此预处理二维数组： \[ \text{mx}[i][j] = \max_{k=i}^{j} \text{arr}[k] \] 该数组可以在 \(O(n^2)\) 时间内完成。

五、状态转移方程（核心）

对于区间 \([i, j]\)，枚举最后一次分割点 \(k\)： \[ i \le k < j \] 将区间分为左右两部分：

  • 左子树：\([i, k]\)
  • 右子树：\([k+1, j]\)

此时：

  • 左子树的最小代价为：\(f[i][k]\)
  • 右子树的最小代价为：\(f[k+1][j]\)
  • 当前根节点的代价为：

\[ \max(\text{arr}[i..k]) \times \max(\text{arr}[k+1..j]) \]

因此状态转移为： \[ f[i][j] = \min_{i \le k < j} \left( f[i][k] + f[k+1][j] + \text{mx}[i][k] \cdot \text{mx}[k+1][j] \right) \]

六、DP 计算顺序

由于 \(f[i][j]\) 依赖于更短的区间，必须按区间长度递增的顺序计算：

  1. 枚举区间长度 len = 2 .. n
  2. 枚举区间右端点 j
  3. 计算左端点 i = j - len + 1
  4. 枚举分割点 k

最终答案为： \[ f[0][n-1] \]

七、复杂度分析

  • 预处理区间最大值：\(O(n^2)\)
  • 区间 DP：三重循环 \(O(n^3)\)

由于题目中 \(n \le 40\)，该复杂度完全可以接受。

八、AC代码

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {

        int n = arr.size();

        // mx[i][j] 表示 arr[i..j] 区间内的最大值
        int mx[45][45];
        for (int i = 0; i < n; ++i) {
            mx[i][i] = arr[i];
            for (int j = i + 1; j < n; ++j) {
                mx[i][j] = max(mx[i][j - 1], arr[j]);
            }
        }

        // f[i][j] 表示区间 [i, j] 构成子树的最小代价
        // 默认初始化为 0，对应 f[i][i] = 0
        int f[45][45] = {};

        // 枚举区间长度
        for (int len = 2; len <= n; ++len) {

            // 枚举区间右端点 j
            for (int j = len - 1; j < n; ++j) {

                // 由长度反推出左端点 i
                int i = j - len + 1;

                // 用较大的初值初始化，避免溢出
                int mi = INT_MAX >> 1;

                // 枚举分割点 k
                for (int k = i; k < j; ++k) {
                    mi = min(
                        mi,
                        f[i][k]
                        + f[k + 1][j]
                        + mx[i][k] * mx[k + 1][j]
                    );
                }

                // 得到区间 [i, j] 的最优值
                f[i][j] = mi;
            }
        }

        // 整个区间的最小代价
        return f[0][n - 1];
    }
};