§1

题目描述

把规则拆清楚:叶子是 arr 里的数,按从左到右的中序顺序排好,顺序锁死不能换。每个内部节点都恰好有两个孩子,它的值 = 左边那片叶子的最大值 × 右边那片叶子的最大值。我们要让所有内部节点的值之和最小。关键约束是叶子顺序固定,所以建树其实就是在相邻的位置上,反复把一段叶子切成左右两块,递归地拼。提示里 2 ≤ arr.length ≤ 40,每个数 1 ≤ arr[i] ≤ 15。

输入 = arr = [4,11]　输出 = 44(只有一种树,根 = 4×11)

输入 = arr = [6,2,4]　输出 = 32(两种树里更小的那个)

输入 = 本节演示 arr = [6,2,4,5]　输出 = 58

§2

思路解析

一句话答案：LeetCode 1130 叶值的最小代价生成树：叶子顺序锁死，内部节点值=左右两块最大叶之积，求和最小。用区间 DP，dp[i][j] 枚举切点取左段+右段+两块最大叶之积的最小，时间 O(n³)、空间 O(n²)。

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

给一个正整数数组 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。

▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开

记住这条转移:一段叶子拆成左右两块,代价 = 左块代价 + 右块代价 + 两块最大叶的乘积。枚举所有切法取最小,就是这段的 dp 值。

总览 · 先把对角线 dp[i][i] 全填 0：这是一张 4×4 的 dp 表,行号 i、列号 j,只有 i ≤ j 的右上三角有意义。先看对角线:dp[0][0]、dp[1][1] 一直到 dp[3][3],它们都是单个叶子,自己就是叶子、没有内部节点,代价全是 0。我们要的答案在最右上角 dp[0][3],也就是整段 [6,2,4,5] 的最优解。填表的顺序是从短区间到长区间,因为长区间要用到短区间的结果。

核心 · 一个根的代价怎么算：先把每个内部节点的代价讲透。任意一段叶子切成左右两块后,接它俩的那个根,值就是左块里最大的叶子乘以右块里最大的叶子。比如把 [6] 和 [2] 接起来,根就是 6 乘 2 等于 12。注意取的是每一块的最大叶子,不是整段的最大值,也不是叶子之和。后面每一格 dp 都在反复用这条规则。

考察 dp[0][1] · 长度 2 的区间：轮到算 dp[0][1],也就是叶子 [6,2] 这一段。它要在中间选一个缝隙 k 切成左右两块,缝隙可以在 0 到 0 之间。每个切法都得算一遍代价,然后取最小的那个。

dp[0][1] · 试切点 k=0：切点 k=0,把 [6,2] 切成左块 [6] 和右块 [2]。左块最优是 dp[0][0]=0,右块是 dp[1][1]=0,再加上接它俩的根 6 乘 2 等于 12。三项相加 12。先记下这个候选。

记入 dp[0][1] = 12：所有切法比完:k=0→12。最小的是 k=0 给出的 12,把它写进 dp[0][1]。这一格定下来了,后面更长的区间就能直接拿它当左块或右块用。

考察 dp[1][2] · 长度 2 的区间：轮到算 dp[1][2],也就是叶子 [2,4] 这一段。它要在中间选一个缝隙 k 切成左右两块,缝隙可以在 1 到 1 之间。每个切法都得算一遍代价,然后取最小的那个。

dp[1][2] · 试切点 k=1：切点 k=1,把 [2,4] 切成左块 [2] 和右块 [4]。左块最优是 dp[1][1]=0,右块是 dp[2][2]=0,再加上接它俩的根 2 乘 4 等于 8。三项相加 8。先记下这个候选。

记入 dp[1][2] = 8：所有切法比完:k=1→8。最小的是 k=1 给出的 8,把它写进 dp[1][2]。这一格定下来了,后面更长的区间就能直接拿它当左块或右块用。

考察 dp[2][3] · 长度 2 的区间：轮到算 dp[2][3],也就是叶子 [4,5] 这一段。它要在中间选一个缝隙 k 切成左右两块,缝隙可以在 2 到 2 之间。每个切法都得算一遍代价,然后取最小的那个。

dp[2][3] · 试切点 k=2：切点 k=2,把 [4,5] 切成左块 [4] 和右块 [5]。左块最优是 dp[2][2]=0,右块是 dp[3][3]=0,再加上接它俩的根 4 乘 5 等于 20。三项相加 20。先记下这个候选。

记入 dp[2][3] = 20：所有切法比完:k=2→20。最小的是 k=2 给出的 20,把它写进 dp[2][3]。这一格定下来了,后面更长的区间就能直接拿它当左块或右块用。

考察 dp[0][2] · 长度 3 的区间：轮到算 dp[0][2],也就是叶子 [6,2,4] 这一段。它要在中间选一个缝隙 k 切成左右两块,缝隙可以在 0 到 1 之间。每个切法都得算一遍代价,然后取最小的那个。

dp[0][2] · 试切点 k=0：切点 k=0,把 [6,2,4] 切成左块 [6] 和右块 [2,4]。左块最优是 dp[0][0]=0,右块是 dp[1][2]=8,再加上接它俩的根 6 乘 4 等于 24。三项相加 32。先记下这个候选。

dp[0][2] · 试切点 k=1：切点 k=1,把 [6,2,4] 切成左块 [6,2] 和右块 [4]。左块最优是 dp[0][1]=12,右块是 dp[2][2]=0,再加上接它俩的根 6 乘 4 等于 24。三项相加 36。比当前最优 32 大,这个切法不划算。

记入 dp[0][2] = 32：所有切法比完:k=0→32, k=1→36。最小的是 k=0 给出的 32,把它写进 dp[0][2]。这一格定下来了,后面更长的区间就能直接拿它当左块或右块用。

考察 dp[1][3] · 长度 3 的区间：轮到算 dp[1][3],也就是叶子 [2,4,5] 这一段。它要在中间选一个缝隙 k 切成左右两块,缝隙可以在 1 到 2 之间。每个切法都得算一遍代价,然后取最小的那个。

dp[1][3] · 试切点 k=1：切点 k=1,把 [2,4,5] 切成左块 [2] 和右块 [4,5]。左块最优是 dp[1][1]=0,右块是 dp[2][3]=20,再加上接它俩的根 2 乘 5 等于 10。三项相加 30。先记下这个候选。

dp[1][3] · 试切点 k=2：切点 k=2,把 [2,4,5] 切成左块 [2,4] 和右块 [5]。左块最优是 dp[1][2]=8,右块是 dp[3][3]=0,再加上接它俩的根 4 乘 5 等于 20。三项相加 28。比之前的 30 还小,刷新最优。

记入 dp[1][3] = 28：所有切法比完:k=1→30, k=2→28。最小的是 k=2 给出的 28,把它写进 dp[1][3]。这一格定下来了,后面更长的区间就能直接拿它当左块或右块用。

考察 dp[0][3] · 长度 4 的区间：轮到算 dp[0][3],也就是叶子 [6,2,4,5] 这一段。它要在中间选一个缝隙 k 切成左右两块,缝隙可以在 0 到 2 之间。每个切法都得算一遍代价,然后取最小的那个。

dp[0][3] · 试切点 k=0：切点 k=0,把 [6,2,4,5] 切成左块 [6] 和右块 [2,4,5]。左块最优是 dp[0][0]=0,右块是 dp[1][3]=28,再加上接它俩的根 6 乘 5 等于 30。三项相加 58。先记下这个候选。

dp[0][3] · 试切点 k=1：切点 k=1,把 [6,2,4,5] 切成左块 [6,2] 和右块 [4,5]。左块最优是 dp[0][1]=12,右块是 dp[2][3]=20,再加上接它俩的根 6 乘 5 等于 30。三项相加 62。比当前最优 58 大,这个切法不划算。

dp[0][3] · 试切点 k=2：切点 k=2,把 [6,2,4,5] 切成左块 [6,2,4] 和右块 [5]。左块最优是 dp[0][2]=32,右块是 dp[3][3]=0,再加上接它俩的根 6 乘 5 等于 30。三项相加 62。比当前最优 58 大,这个切法不划算。

记入 dp[0][3] = 58：所有切法比完:k=0→58, k=1→62, k=2→62。最小的是 k=0 给出的 58,把它写进 dp[0][3]。这一格定下来了,后面更长的区间就能直接拿它当左块或右块用。

完成 · 答案 58：整张表填满了,右上角 dp[0][3] = 58 就是最终答案。回看这条最优路线:先把中间的小叶子 2 和它较小的邻居配掉,再让 4 跟较小的邻居配,最后剩 6 和 5 接到根,层层乘积加起来正好 58。叶子越小越早被乘掉、乘的邻居越小越省,这就是为什么最优解长这样。

边界都能手验:两片叶子只有一种树;三片叶子比两种切法;全 1 时每个根都是 1×1。

面试三连:状态设成区间 dp[i][j] 加切点枚举;可用单调栈优化到 O(n);最大叶用预处理表或递归返回值都行。

§3

参考代码

from __future__ import annotationsfrom 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]

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：O(n³)，一共约 n² 个区间状态 dp[i][j],每个状态要枚举最多 n 个切点 k,所以是 n² × n。题目 n ≤ 40,完全够用
空间：O(n²)，按峰值算:dp 备忘表 n×n,C++/Java 还有一张同样大小的最大叶表 g,都是平方级。自顶向下递归再额外占 O(n) 栈深

§5

易错点

✗ 错误写法：以为可以随意给叶子配对、打乱顺序建树

✓ 正确写法：叶子的中序顺序锁死,只能在相邻区间里切

题目要求叶子按 arr 顺序做中序遍历,所以建树等价于不断把一段相邻叶子切成左右两块

✗ 错误写法：把根的值算成两块叶子之和,或整段的最大值

✓ 正确写法：根 = 左块最大叶 × 右块最大叶,是乘积,且各取各块的最大

内部节点定义就是左右子树最大叶的乘积,取错成和或取错范围,结果全错

✗ 错误写法：照搬 C++ 那句 f[i][j] 大于 0 当已算标记到别的题

✓ 正确写法：只有当区间代价必为正时这个哨兵才安全

本题长度 ≥ 2 的区间代价一定大于 0、单叶返回 0 不写表,所以 0 不会和已算混淆;代价可能为 0 的题要改用 null 或单独的 visited 标记

面试追问把动画讲成自己的话

追问这题为什么是区间 DP,状态怎么设?

因为叶子的中序顺序固定,建树等价于不断把一段相邻叶子切成左右两半,天然带「区间」结构。设 dp[i][j] 为只用叶子 arr[i..j] 拼树的最小内部节点和,枚举切点 k 把区间分成 [i,k] 和 [k+1,j],转移是 dp[i][k] + dp[k+1][j] + 左块最大叶乘右块最大叶。答案是 dp[0][n-1],复杂度 O(n³)。

追问能不能优化到更快?

能。有一个 O(n) 的单调栈贪心:维护一个递减栈,每遇到一个比栈顶大的叶子,就把栈顶这个较小的叶子弹出,它必然要和左右两个邻居里较小的那个相乘,把这个乘积累加进答案。直觉是越小的叶子越早乘掉、且要乘尽量小的邻居最省。区间 DP 更通用好想,单调栈更快,面试里能说清两者关系是加分项。

追问左右块的最大叶子怎么高效拿到?

两种办法。一是像 C++、Java 那样预处理一张 g[i][j] 表,g[i][j] = max(g[i][j-1], arr[j]),O(n²) 建好后查表是 O(1)。二是像 Python 那样让递归函数顺带返回这一段的最大叶子,父调用直接用返回值相乘,省掉单独的表。两种都对,看习惯。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 动态规划套路 61/108

最大的以 1 为边界的正方形

LeetCode 1139 · 中等 · 沿着动态规划套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

899道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

from __future__ import annotationsfrom 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]