题目描述
思路解析动画文字版
记住这条转移:一段叶子拆成左右两块,代价 = 左块代价 + 右块代价 + 两块最大叶的乘积。枚举所有切法取最小,就是这段的 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);最大叶用预处理表或递归返回值都行。
参考代码
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]复杂度
- 时间：O(n³)，一共约 n² 个区间状态 dp[i][j],每个状态要枚举最多 n 个切点 k,所以是 n² × n。题目 n ≤ 40,完全够用
- 空间：O(n²)，按峰值算:dp 备忘表 n×n,C++/Java 还有一张同样大小的最大叶表 g,都是平方级。自顶向下递归再额外占 O(n) 栈深
易错点
面试追问把动画讲成自己的话
追问这题为什么是区间 DP,状态怎么设?
追问能不能优化到更快?
追问左右块的最大叶子怎么高效拿到?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大的以 1 为边界的正方形
LeetCode 1139 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题