区间动态规划例题：最优字母二叉树问题（Huffman树扩展版本） 题目描述如下： 给定一个包含 n 个不同字符的集合，字符 \(c_ i\) 的出现频率为 \(f_ i\)，同时已知任意两个字符 \(c_ i\) 和 \(c_ j\) 的合并成本为 \(cost(c_ i, c_ j)\)。我们要构建一棵二叉树，其中每个叶子节点对应一个字符，每个内部节点对应一次合并操作（将两个子树合并），合并两个子树对应的字符集合的成本定义为这两个集合中任意两个字符之间的最大合并成本（即：设左子树包含字符集 \(L\)，右子树包含字符集 \(R\)，合并成本为 \(\max_ {a \in L, b \in R} cost(a, b)\)）。整棵树的构建总成本等于所有内部节点的合并成本之和。求构建二叉树的最小总成本。 逐步讲解 1. 问题理解 这是一个区间动态规划问题，因为我们可以将字符按某个顺序排列（比如按字符编号或字母顺序），然后每次合并相邻的字符区间。 题目中，字符的顺序是固定的（可以任意指定顺序，但通常给定顺序后就不能改变，否则问题会变得更复杂）。这里假设字符已经按某种顺序排列好（例如按字符标签升序），我们只允许合并相邻的区间。 关键点在于： 每个节点对应一个字符集合（区间）。 合并两个相邻区间 \([ l, m]\) 和 \([ m+1, r ]\) 时，合并成本是左区间中任意字符和右区间中任意字符之间的最大 \(cost\) 值。 总成本是每次合并的成本累加。 2. 状态定义 设 \(dp[ l][ r]\) 表示将区间 \([ l, r ]\) 内的所有字符合并成一棵子树的最小总成本。 当区间只有一个字符时，不需要合并，成本为 0。 目标：求 \(dp[ 1][ n ]\)。 3. 状态转移 考虑最后一次合并：将区间 \([ l, r]\) 分成两个子区间 \([ l, k]\) 和 \([ k+1, r ]\)，分别建树，然后合并这两棵树。 合并成本为： \[ mergeCost(l, k, r) = \max_ {i \in [ l, k], \; j \in [ k+1, r]} cost(c_ i, c_ j) \] 这个值可以预处理出来，记作 \(maxCost[ l][ k][ r ]\)。 则状态转移方程为： \[ dp[ l][ r] = \min_ {k=l}^{r-1} \left( dp[ l][ k] + dp[ k+1][ r ] + mergeCost(l, k, r) \right) \] 其中 \(dp[ l][ l ] = 0\)。 4. 预处理合并成本 为了快速得到 \(mergeCost(l, k, r)\)，我们可以用动态规划思想预处理一个二维数组 \(maxBetween[ i][ j]\) 表示字符 \(c_ i\) 到 \(c_ j\) 之间的最大 \(cost\) 值（这里指的是字符对的最大 \(cost\)，但注意我们实际需要的是两个区间之间的最大跨区间成本）。 更直接的方法是： 设 \(maxBetween[ i][ j]\) 为字符 \(i\) 到字符 \(j\) 之间的最大 \(cost(c_ i, c_ j)\)（即固定顺序下，区间内任意两字符的最大成本）。 但我们需要的是左区间 \([ l, k]\) 和右区间 \([ k+1, r ]\) 之间的最大成本，这等于： \[ mergeCost(l, k, r) = \max( maxBetween[ l][ k], maxBetween[ k+1][ r], \max_ {i \in [ l, k], j \in [ k+1, r]} cost(c_ i, c_ j) ) \] 但注意 \(maxBetween\) 定义是区间内任意两字符的最大成本，而我们需要的跨区间最大成本可以这样算： 定义二维表 \(crossMax[ l][ r]\) 为区间 \([ l, r]\) 内所有字符对之间的最大 \(cost\)，显然 \(crossMax[ l][ r] = \max(crossMax[ l][ r-1], \max_ {i=l}^{r-1} cost(c_ i, c_ r))\)，可以 \(O(n^2)\) 预处理。 但跨区间最大成本实际上是整个区间 \([ l, r]\) 的 \(crossMax[ l][ r ]\) 去掉区间内各自内部的最大值？不对。 更简单的方法：我们直接预处理一个三维数组 \(maxAcross[ l][ k][ r]\) 表示左区间 \([ l, k]\) 和右区间 \([ k+1, r ]\) 之间的最大 \(cost\)，可以在 \(O(n^3)\) 时间内预处理。 但 \(n\) 较小时可接受（\(n \leq 100\) 时 \(O(n^3)\) 可行）。 预处理方法： 对每个 \(l, r\)，先算出区间内所有字符对的最大 \(cost\) 的二维表 \(maxInRange[ l][ r ]\)，用 DP： \(maxInRange[ l][ r] = \max( maxInRange[ l][ r-1], \max_ {i=l}^{r} cost(c_ i, c_ r) )\)，其中 \(maxInRange[ l][ l ] = 0\)（单个字符内部无成本）。 但实际上区间内部最大成本在合并时不需要，我们需要的是跨区间最大成本。 跨区间最大成本可以这样算： 设 \(maxAcross[ l][ k][ r] = \max_ {i \in [ l, k], j \in [ k+1, r]} cost(c_ i, c_ j)\)。 可以枚举 \(i, j\) 在 \(O(n^4)\) 算，但太慢。 优化：固定 \(l, r\)，我们可以用递推： \(maxAcross[ l][ k][ r] = \max( maxAcross[ l][ k-1][ r], \max_ {j=k+1}^{r} cost(c_ k, c_ j) )\) 但这样还是要 \(O(n^3)\) 预处理，但比 \(O(n^4)\) 好。 更好的方法：我们并不需要显式存三维数组，在 DP 时直接计算跨区间最大成本。 对固定的 \(l, r\)，我们可以先预处理数组 \(rowMax[ i][ j] = \max_ {k=i}^{j} cost(c_ i, c_ k)\)，然后跨区间最大成本可以拆成左区间取一个 \(i\)，右区间取一个 \(j\)，使得 \(cost\) 最大。 但这样在 DP 时仍需 \(O(n)\) 时间计算，总复杂度 \(O(n^4)\) 太高。 所以我们考虑简化：题目中合并成本定义为两集合间任意两字符的最大 \(cost\)，这等价于整个大区间 \([ l, r ]\) 内所有字符对的最大 \(cost\) 值（因为跨区间的最大成本不会小于区间内部的最大成本，而合并时我们关心的是跨区间的最大值）。 但注意：合并成本只取决于该次合并的左右子树，而左右子树内部的字符对成本在更早的合并中已经计算过了（不重复计算）。 所以这里合并成本是 本次合并 涉及的左右区间之间的字符对最大成本，与区间内部无关。 为了快速得到这个值，我们可以预处理一个二维数组 \(maxBetween[ i][ j]\) 表示字符 \(i\) 和 \(j\) 之间的 \(cost\)，然后跨区间最大成本就是 \(\max_ {i \in [ l, k], j \in [ k+1, r ]} cost(i, j)\)。 这个可以在 \(O(n^3)\) 预处理： 对每个 \(l, r\)，枚举分割点 \(k\)，用 \(O(n)\) 时间计算最大跨区间成本，总 \(O(n^4)\) 太大。 但我们可以用前缀最大值优化： 预处理一个数组 \(preMax[ i][ j] = \max_ {t=1}^{j} cost(c_ i, c_ t)\)，则 \(\max_ {i \in [ l, k], j \in [ k+1, r]} cost(i,j) = \max_ {i=l}^{k} ( \max_ {j=k+1}^{r} cost(i,j) ) = \max_ {i=l}^{k} preMax[ i][ r]\) （其中 \(preMax[ i][ r ]\) 是 \(i\) 到 \(r\) 的最大 \(cost\)，但只对 \(j \le r\)）。 我们可以用 \(O(n^2)\) 预处理 \(preMax[ i][ j ]\)，然后在 DP 时对每个 \(l, k, r\) 用 \(O(k-l+1) = O(n)\) 时间求最大值，总复杂度 \(O(n^4)\) 仍然高。 再优化：我们可以预处理 \(maxCostFromTo[ l][ r] = \max_ {i=l}^{r} \max_ {j=i+1}^{r} cost(i,j)\) 吗？这不对。 鉴于题目可能 n 不大（比如 n ≤ 50），我们可以接受 \(O(n^3)\) 的 DP，而合并成本计算如果每次 \(O(n)\) 就是 \(O(n^4)\)，可能勉强可过。 但为了更优，我们换一种思路：合并成本实际上等于整个区间 \([ l, r ]\) 内的最大 \(cost\) 值（因为任意两字符的最大成本必然出现在某次合并的跨区间中，而该次合并的成本就是它）。 我们来验证：设整个区间内最大 \(cost\) 是 \(cost(c_ p, c_ q)\)，且 \(p < q\)。那么在合并过程中，当 \(p\) 和 \(q\) 第一次被分到不同子树时，那次合并的成本必然包含 \(cost(c_ p, c_ q)\)，而且由于是最大值，那次合并的成本就是它。而且更大值不会更早出现。 所以实际上， 合并总成本等于区间内所有不同字符对的最大 \(cost\) 值之和，但每个字符对的最大值只在它第一次被分开的合并时计算一次 。 那么问题转化为：每次合并时，成本=跨区间最大 \(cost\)，而跨区间最大 \(cost\) 就是该次合并涉及的左右子树中所有字符对的最大 \(cost\)。 可以这样设计状态转移： 设 \(maxCost[ l][ r]\) 表示区间 \([ l, r ]\) 内所有字符对的最大 \(cost\) 值，可以 \(O(n^2)\) 预处理。 但注意：合并 \([ l, k]\) 和 \([ k+1, r]\) 时，合并成本 = \(\max( maxCost[ l][ k], maxCost[ k+1][ r], maxAcross[ l][ k][ r ] )\)，其中 \(maxAcross\) 是跨区间最大 \(cost\)。 而跨区间最大 \(cost\) 可以这样算： \[ maxAcross[ l][ k][ r] = \max( maxCost[ l][ r ], - ??) \text{ 不对} \] 实际上，\(maxCost[ l][ r ]\) 已经包含了跨区间的最大值。 而且 \(maxCost[ l][ r] = \max( maxCost[ l][ k], maxCost[ k+1][ r], maxAcross[ l][ k][ r ] )\)。 因此在合并时，合并成本 = \(maxCost[ l][ r]\) 当且仅当 \(maxCost[ l][ r ]\) 对应的字符对恰好一个在左、一个在右。 但如果不是，则合并成本可能小于 \(maxCost[ l][ r ]\)。 所以不能直接用 \(maxCost[ l][ r ]\) 作为合并成本。 为了避免复杂化，我们回到基础方法：在 DP 时，对每个分割点 \(k\)，用 \(O(n^2)\) 时间计算跨区间最大成本，总复杂度 \(O(n^4)\)。 如果 n ≤ 50，\(50^4 = 6.25\times 10^6\)，可接受。 我们就用这个方法。 5. 最终算法步骤 (1) 输入字符频率（本题频率其实没用，因为成本与频率无关，只与字符对 cost 有关），以及字符对成本矩阵 \(cost[ i][ j ]\)。 (2) 初始化 \(dp[ l][ r ] = 0\) 当 \(l == r\)。 (3) 枚举区间长度 len 从 2 到 n： - 枚举左端点 l，r = l + len - 1。 - 初始化 dp[ l][ r ] = INF。 - 枚举分割点 k 从 l 到 r-1： 计算跨区间最大成本 cross = 0 for i in [ l, k ] for j in [ k+1, r ] cross = max(cross, cost[ i][ j ]) 合并成本 = cross dp[ l][ r] = min(dp[ l][ r], dp[ l][ k] + dp[ k+1][ r ] + cross) (4) 输出 dp[ 1][ n ]。 6. 时间复杂度 计算跨区间成本为 \(O(n^2)\)，总复杂度 \(O(n^4)\)。 可以优化：预处理 \(maxCost[ i][ j ]\) 为字符 i 到 j 的最大成本，但跨区间最大成本需要特殊计算，不过可以优化到 \(O(n^3)\)，但为了清晰，我们先用 \(O(n^4)\) 版本。 7. 示例 假设 3 个字符 A, B, C，cost 矩阵： cost(A,B)=2, cost(A,C)=5, cost(B,C)=3。 区间 [ 1,3 ]： 分割点 k=1：左 [ A]，右 [ B,C]。跨区间最大成本 = max(cost(A,B), cost(A,C)) = 5。总成本 = 0 + dp[ 2][ 3 ] + 5。 计算 dp[ 2][ 3]：区间 [ B,C ]，跨区间成本 = cost(B,C)=3。总成本=0+0+3=3。 所以 dp[ 1][ 3 ] 候选 = 5+3=8。 分割点 k=2：左 [ A,B]，右 [ C ]。跨区间最大成本 = max(cost(A,C), cost(B,C)) = 5。 dp[ 1][ 2]：区间 [ A,B ]，跨区间成本=2，总成本=0+0+2=2。 所以总成本候选 = 2 + 0 + 5 = 7。 取最小 7。 因此最小总成本 = 7。 这个题目是 Huffman 树的扩展，将合并成本改为两子树中字符对的最大 cost，并用区间 DP 求解。