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

这道题到底在问什么

输入

arr = [4,11]

输出

44(只有一种树,根 = 4×11)

输入

arr = [6,2,4]

输出

32(两种树里更小的那个)

输入

本节演示 arr = [6,2,4,5]

输出

58

先想最直接的笨办法

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

最优解：一步一步想明白

1. 3记住这条转移:一段叶子拆成左右两块,代价 = 左块代价 + 右块代价 + 两块最大叶的乘积。枚举所有切法取最小,就是这段的 dp 值。
2. 4这是一张 4×4 的 dp 表,行号 i、列号 j,只有 i ≤ j 的右上三角有意义。先看对角线:dp[0][0]、dp[1][1] 一直到 dp[3][3],它们都是单个叶子,自己就是叶子、没有内部节点,代价全是 0。我们要的答案在最右上角 dp[0][3],也就是整段 [6,2,4,5] 的最优解。填表的顺序是从短区间到长区间,因为长区间要用到短区间的结果。
3. 5先把每个内部节点的代价讲透。任意一段叶子切成左右两块后,接它俩的那个根,值就是左块里最大的叶子乘以右块里最大的叶子。比如把 [6] 和 [2] 接起来,根就是 6 乘 2 等于 12。注意取的是每一块的最大叶子,不是整段的最大值,也不是叶子之和。后面每一格 dp 都在反复用这条规则。
4. 6轮到算 dp[0][1],也就是叶子 [6,2] 这一段。它要在中间选一个缝隙 k 切成左右两块,缝隙可以在 0 到 0 之间。每个切法都得算一遍代价,然后取最小的那个。
5. 7切点 k=0,把 [6,2] 切成左块 [6] 和右块 [2]。左块最优是 dp[0][0]=0,右块是 dp[1][1]=0,再加上接它俩的根 6 乘 2 等于 12。三项相加 12。先记下这个候选。
6. 8所有切法比完:k=0→12。最小的是 k=0 给出的 12,把它写进 dp[0][1]。这一格定下来了,后面更长的区间就能直接拿它当左块或右块用。
7. 9轮到算 dp[1][2],也就是叶子 [2,4] 这一段。它要在中间选一个缝隙 k 切成左右两块,缝隙可以在 1 到 1 之间。每个切法都得算一遍代价,然后取最小的那个。
8. 10切点 k=1,把 [2,4] 切成左块 [2] 和右块 [4]。左块最优是 dp[1][1]=0,右块是 dp[2][2]=0,再加上接它俩的根 2 乘 4 等于 8。三项相加 8。先记下这个候选。
9. 11所有切法比完:k=1→8。最小的是 k=1 给出的 8,把它写进 dp[1][2]。这一格定下来了,后面更长的区间就能直接拿它当左块或右块用。
10. 12轮到算 dp[2][3],也就是叶子 [4,5] 这一段。它要在中间选一个缝隙 k 切成左右两块,缝隙可以在 2 到 2 之间。每个切法都得算一遍代价,然后取最小的那个。
11. 13切点 k=2,把 [4,5] 切成左块 [4] 和右块 [5]。左块最优是 dp[2][2]=0,右块是 dp[3][3]=0,再加上接它俩的根 4 乘 5 等于 20。三项相加 20。先记下这个候选。
12. 14所有切法比完:k=2→20。最小的是 k=2 给出的 20,把它写进 dp[2][3]。这一格定下来了,后面更长的区间就能直接拿它当左块或右块用。
13. 15轮到算 dp[0][2],也就是叶子 [6,2,4] 这一段。它要在中间选一个缝隙 k 切成左右两块,缝隙可以在 0 到 1 之间。每个切法都得算一遍代价,然后取最小的那个。
14. 16切点 k=0,把 [6,2,4] 切成左块 [6] 和右块 [2,4]。左块最优是 dp[0][0]=0,右块是 dp[1][2]=8,再加上接它俩的根 6 乘 4 等于 24。三项相加 32。先记下这个候选。
15. 17切点 k=1,把 [6,2,4] 切成左块 [6,2] 和右块 [4]。左块最优是 dp[0][1]=12,右块是 dp[2][2]=0,再加上接它俩的根 6 乘 4 等于 24。三项相加 36。比当前最优 32 大,这个切法不划算。
16. 18所有切法比完:k=0→32, k=1→36。最小的是 k=0 给出的 32,把它写进 dp[0][2]。这一格定下来了,后面更长的区间就能直接拿它当左块或右块用。
17. 19轮到算 dp[1][3],也就是叶子 [2,4,5] 这一段。它要在中间选一个缝隙 k 切成左右两块,缝隙可以在 1 到 2 之间。每个切法都得算一遍代价,然后取最小的那个。
18. 20切点 k=1,把 [2,4,5] 切成左块 [2] 和右块 [4,5]。左块最优是 dp[1][1]=0,右块是 dp[2][3]=20,再加上接它俩的根 2 乘 5 等于 10。三项相加 30。先记下这个候选。
19. 21切点 k=2,把 [2,4,5] 切成左块 [2,4] 和右块 [5]。左块最优是 dp[1][2]=8,右块是 dp[3][3]=0,再加上接它俩的根 4 乘 5 等于 20。三项相加 28。比之前的 30 还小,刷新最优。
20. 22所有切法比完:k=1→30, k=2→28。最小的是 k=2 给出的 28,把它写进 dp[1][3]。这一格定下来了,后面更长的区间就能直接拿它当左块或右块用。
21. 23轮到算 dp[0][3],也就是叶子 [6,2,4,5] 这一段。它要在中间选一个缝隙 k 切成左右两块,缝隙可以在 0 到 2 之间。每个切法都得算一遍代价,然后取最小的那个。
22. 24切点 k=0,把 [6,2,4,5] 切成左块 [6] 和右块 [2,4,5]。左块最优是 dp[0][0]=0,右块是 dp[1][3]=28,再加上接它俩的根 6 乘 5 等于 30。三项相加 58。先记下这个候选。
23. 25切点 k=1,把 [6,2,4,5] 切成左块 [6,2] 和右块 [4,5]。左块最优是 dp[0][1]=12,右块是 dp[2][3]=20,再加上接它俩的根 6 乘 5 等于 30。三项相加 62。比当前最优 58 大,这个切法不划算。
24. 26切点 k=2,把 [6,2,4,5] 切成左块 [6,2,4] 和右块 [5]。左块最优是 dp[0][2]=32,右块是 dp[3][3]=0,再加上接它俩的根 6 乘 5 等于 30。三项相加 62。比当前最优 58 大,这个切法不划算。
25. 27所有切法比完:k=0→58, k=1→62, k=2→62。最小的是 k=0 给出的 58,把它写进 dp[0][3]。这一格定下来了,后面更长的区间就能直接拿它当左块或右块用。
26. 28整张表填满了,右上角 dp[0][3] = 58 就是最终答案。回看这条最优路线:先把中间的小叶子 2 和它较小的邻居配掉,再让 4 跟较小的邻居配,最后剩 6 和 5 接到根,层层乘积加起来正好 58。叶子越小越早被乘掉、乘的邻居越小越省,这就是为什么最优解长这样。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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]

#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);
    }
};

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;
    }
}

复杂度

面试官可能追问