叶值的最小代价生成树 图解题解

叶值的最小代价生成树，究竟在求什么

给一个正整数数组 arr，把这些数当二叉树的叶子（二叉树=每个点最多两个孩子，最下面不分叉的点叫叶子），叶子从左到右的顺序必须和数组一致、不能打乱。每个非叶节点（有两孩子的内部节点）的值=左边叶子的最大值乘右边叶子的最大值。所有能搭出的树里，要让全部非叶节点值之和最小。本文用 arr=[6,2,4,5] 演示，最小和 58。

把每种搭法都试一遍，为什么算不完

n 片叶子能搭出的不同二叉树按卡特兰数（随规模指数级暴涨的组合数）疯长，n=40 已是天文数字，逐棵枚举跑不完。更要命的是重复：算整段 [6,2,4,5] 时，子段 [2,4] 的最优代价会在多棵大树里各算一遍。

既然子段最优解反复被用，就算一次存起来，这就是动态规划（把每段叶子的最优代价先算好存下，更长区间直接取用）。所以叫区间 DP（状态=每步要盯住的量，这里是一段叶子的端点 [i,j]）。大 O 记号（描述规模变大时运算量怎么涨）把指数枚举压回 O(n³)。

状态定成一段区间，dp[i][j] 存的是什么

把 dp[i][j] 定义成：只用第 i 到第 j 这段叶子搭树的最小非叶节点值之和。（i,j）是表的（行号，列号），从 0 数起，只有 i≤j 的右上三角有意义。对角线 dp[i][i] 是单独一片叶子，没有内部节点、代价 0，是不用再往下拆的最简单情况（base case）。答案在最右上角 dp[0][n-1]，填表从短区间到长区间。

切点怎么枚举，根的那笔乘积从哪来

算 dp[i][j] 时，在这段叶子中间选一条缝隙切成左块 [i,k] 和右块 [k+1,j]。左块最优代价 dp[i][k]、右块 dp[k+1][j]，接起两块的根值=左块最大叶乘右块最大叶（每块各取最大叶，题目规定），即 max(i..k)×max(k+1..j)，三项相加是这种切法的代价。缝隙落在 i 到 j-1 的任意位置，取所有切法的最小就是 dp[i][j]。

拿 [6,2,4,5] 亲手把 dp 表填一遍

四片单叶先填 0。长度 2 只有一种切法：[6,2] 得 6×2=12，[2,4] 得 2×4=8，[4,5] 得 4×5=20。

长度 3 比两种切法。[6,2,4] 在 6 后切 0+8+6×4=32、在 2 后切 12+0+6×4=36，取 32；[2,4,5] 在 2 后切 0+20+2×5=30、在 4 后切 8+0+4×5=28，取 28。

整段 [6,2,4,5] 比三种：在 6 后切 0+28+6×5=58、在 2 后切 12+20+6×5=62、在 4 后切 32+0+6×5=62，最小 58 就是答案，和题面对上。

根写成两块之和，dp[0][1] 为什么从 12 塌成 8

复杂度：区间约 n² 个，每个枚举最多 n 个切点，时间 O(n³)；dp 表 n×n，空间 O(n²)，n≤40 够用。

根取成两块之和是最常见的错，dp[0][1] 会算成 6+2=8 而不是 6×2=12，答案错到底。也别取成整段最大叶；叶子顺序也不能重排，一换位置最优树就变了。边界也能手验：两片叶子只一种树，全 1 时每根都是 1×1。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> Tuple:
            if i == j:
                return 0, arr[i]
            s, mx = inf, -1
            for k in range(i, j):
                s1, mx1 = dfs(i, k)
                s2, mx2 = dfs(k + 1, j)
                t = s1 + s2 + mx1 * mx2
                if s > t:
                    s = t
                    mx = max(mx1, mx2)
            return s, mx

        return dfs(0, len(arr) - 1)[0]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        int n = arr.size();
        int f[n][n];
        int g[n][n];
        memset(f, 0, sizeof(f));
        for (int i = n - 1; ~i; --i) {
            g[i][i] = arr[i];
            for (int j = i + 1; j < n; ++j) {
                g[i][j] = max(g[i][j - 1], arr[j]);
            }
        }
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (i == j) {
                return 0;
            }
            if (f[i][j] > 0) {
                return f[i][j];
            }
            int ans = 1 << 30;
            for (int k = i; k < j; ++k) {
                ans = min(ans, dfs(i, k) + dfs(k + 1, j) + g[i][k] * g[k + 1][j]);
            }
            return f[i][j] = ans;
        };
        return dfs(0, n - 1);
    }
};

Java

import java.util.*;
class Solution {
    private Integer[][] f;
    private int[][] g;

    public int mctFromLeafValues(int[] arr) {
        int n = arr.length;
        f = new Integer[n][n];
        g = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            g[i][i] = arr[i];
            for (int j = i + 1; j < n; ++j) {
                g[i][j] = Math.max(g[i][j - 1], arr[j]);
            }
        }
        return dfs(0, n - 1);
    }

    private int dfs(int i, int j) {
        if (i == j) {
            return 0;
        }
        if (f[i][j] != null) {
            return f[i][j];
        }
        int ans = 1 << 30;
        for (int k = i; k < j; k++) {
            ans = Math.min(ans, dfs(i, k) + dfs(k + 1, j) + g[i][k] * g[k + 1][j]);
        }
        return f[i][j] = ans;
    }
}