区间动态规划例题：最小成本构建唯一二叉搜索树问题（进阶：带深度限制与操作成本）
字数 6268 2025-12-15 05:47:34

区间动态规划例题：最小成本构建唯一二叉搜索树问题（进阶：带深度限制与操作成本）

题目描述

给定一个由 n 个不同整数组成的排序数组 keys（升序），表示二叉搜索树（BST）中所有节点的键值。同时给定一个长度为 n+1 的数组 freq，其中 freq[i] 表示第 i 个键值（对应 keys[i]）的搜索频率，freq[n] 表示所有不存在于 keys 中的值的搜索频率（即失败搜索的频率，通常对应叶子节点下的空指针）。
此外，还给出以下限制和成本：

  1. 深度限制：树中任何节点的深度不能超过一个给定的整数 maxDepth（根节点深度为 0）。
  2. 操作成本：对每个节点，如果其深度为 d，则访问该节点的成本为 costPerDepth[d]（一个给定数组，长度为 maxDepth+1）。对于失败搜索（即访问空指针），其成本基于其父节点的深度计算（即深度 d 的空指针访问成本为 costPerDepth[d]）。

目标是构建一棵满足深度限制的二叉搜索树，并最小化以下总代价：

\[\text{总代价} = \sum_{i=0}^{n-1} \text{freq}[i] \times (\text{访问键值} \text{keys}[i] \text{的成本}) + \sum_{j=0}^{n} \text{freq}[j] \times (\text{访问第} j \text{个空指针的成本}) \]

其中访问键值的成本等于其节点深度对应的 costPerDepth 值；访问空指针的成本等于其父节点深度对应的 costPerDepth 值（若父节点深度为 d）。

解题思路

这是经典最优二叉搜索树（Optimal BST）问题的扩展，增加了深度限制和基于深度的可变访问成本。
核心挑战在于：在构建BST时，不仅要考虑频率加权路径长度，还要确保树不超过最大深度，且节点的访问成本随深度变化。

  1. 状态定义
    设 dp[l][r][d][k] 表示：用子数组 keys[l..r]（索引从 l 到 r，包含两端）构建一棵满足深度限制的二叉搜索树，且该树的根节点深度恰好为 d，且该树在区间 [l, r] 上构建，同时该树的根节点是区间中的第 k 个元素（即 keys[l + k] 为根，k 从 0 到 r-l）。
    这个状态表示以 keys[l+k] 为根、深度为 d 的BST的最小总代价（包括该子树内所有键值和失败搜索的代价）。
    但这样的状态维度太高（O(n^3 * maxDepth)），需要优化。

  2. 优化状态
    观察到：如果我们固定一个区间 [l, r] 和该区间子树的根深度 d，那么左子树的深度必须为 d+1，右子树深度也为 d+1（因为深度从根向下递增）。因此，我们可以将状态简化为：
    dp[l][r][d] 表示在区间 [l, r] 上构建一棵BST，且该子树根节点的深度为 d 的最小总代价（不再显式指定根是哪个键值，而是在状态转移时枚举根的位置）。
    状态维度：O(n^2 * maxDepth)。

  3. 转移方程
    对于区间 [l, r] 和深度 d：

    • 如果 l > r：表示空子树（只有失败搜索）。此时该空子树对应一个空指针，其父节点深度为 d-1（因为空指针是深度为 d 的节点的子节点，所以其访问成本基于深度 d-1？需要仔细定义）。
      但更合理的定义是：当区间为空时，表示一个失败搜索节点，其访问成本应由其父节点深度 d 决定（因为该空指针是深度为 d 的节点的子节点，所以访问该空指针的成本为 costPerDepth[d]）。
      因此，若 l > r，则 dp[l][r][d] = freq[r+1] * costPerDepth[d]，其中 freq[r+1] 是区间 [l, r] 对应的失败搜索频率（注意：区间 [l, r] 对应失败搜索频率为 freq[l] 到 freq[r+1]，但当区间为空时，应只对应一个失败搜索节点？需要统一处理频率前缀和）。

    为了高效计算总频率，我们预先计算前缀和 psum[i] = sum(freq[0..i])，则区间 [l, r] 内所有键值频率和为 psum[r] - psum[l-1]（若 l>r 则为0），且该区间对应的失败搜索频率总和为 psum[r+1] - psum[l]（包括左端和右端的失败搜索）。

    但更标准的处理是：对于区间 [l, r]，其所有节点（键值和失败搜索）的总频率是固定的，等于 psum[r+1] - psum[l]。
    当我们将区间 [l, r] 以某个键值 keys[m] 为根划分为左区间 [l, m-1] 和右区间 [m+1, r] 时，根节点的深度为 d，访问成本为 costPerDepth[d]。
    左子树根深度为 d+1，右子树根深度也为 d+1。

    因此，转移方程为：

\[ dp[l][r][d] = \min_{m \in [l, r]} \left( dp[l][m-1][d+1] + dp[m+1][r][d+1] + costPerDepth[d] \times \text{totalFreq}(l, r) \right) \]

其中 totalFreq(l, r) = psum[r+1] - psum[l] 是该子树中所有键值和失败搜索的总频率。
注意：根节点 keys[m] 的访问频率已包含在 totalFreq 中（因为它是区间的一部分），所以我们只需在总代价中加上 costPerDepth[d] * totalFreq(l, r) 即可（这实际上将根节点的访问成本按频率加权加入，同时左、右子树的代价在递归中已包含各自的频率加权）。

但这个方程有一个问题：costPerDepth[d] * totalFreq(l, r) 实际上将整个区间的总频率都按深度 d 的成本计算了一次，而左、右子树的代价 dp[l][m-1][d+1] 等又已经包含了它们各自的频率按深度 d+1 计算的成本。这会导致重复计算？让我们仔细分析：

更准确的做法是：dp[l][r][d] 应表示该子树的总代价，其中所有节点的访问成本已经根据其自身深度计算。当我们以 keys[m] 为根时：

  • 根节点的深度为 d，访问成本为 costPerDepth[d]，频率为 freq[m]（注意 freq[m] 是键值频率，不是失败搜索）。
  • 左子树 [l, m-1] 的所有节点深度在 d+1 及以上，其总代价为 dp[l][m-1][d+1]。
  • 右子树 [m+1, r] 类似。
  • 此外，还有两个失败搜索节点：一个在左子树空指针（对应频率 freq[m] 的失败部分？实际上失败搜索频率是连续的：区间 [l, r] 对应的失败搜索频率为 freq[l], ..., freq[r+1]，当我们选择根 m 后，左子树对应失败搜索频率为 freq[l..m]，右子树对应 freq[m+1..r+1]。这些失败搜索的访问成本由它们父节点的深度决定，即左子树空指针的父节点深度为 d，右子树空指针的父节点深度也为 d。因此，这两个失败搜索节点的成本在根节点层面计算，还是归入左右子树？

为了简化，我们采用标准最优BST的动态规划方法，但扩展深度和成本：
设 dp[l][r][d] 表示区间 [l, r] 构建的子树，其根节点的深度为 d，且该子树的总代价（包括所有键值节点和失败搜索节点）的最小值。
转移时，枚举根节点位置 m：

\[ dp[l][r][d] = \min_{m \in [l, r]} \left( dp[l][m-1][d+1] + dp[m+1][r][d+1] + costPerDepth[d] \times freq[m] + \text{额外失败搜索成本} \right) \]

其中 freq[m] 是键值 keys[m] 的频率。
额外失败搜索成本：在根节点 m 处，有两个空指针（左和右），分别对应失败搜索频率 freq[m] 和 freq[m+1]？不对，失败搜索频率数组 freq 的长度为 n+1，索引 i 对应键值 keys[i] 的左空指针（若 i 从0开始）。更标准地：freq[i] 对应在键值 keys[i-1] 和 keys[i] 之间的搜索失败频率（对于 i=0 是小于最小键值的失败搜索，对于 i=n 是大于最大键值的失败搜索）。

为了避免混淆，我们采用经典OBST的DP定义，但加上深度维度。
令 w(l, r) = sum_{i=l}^{r} freq[i] + sum_{j=l}^{r+1} failFreq[j] 是区间 [l, r] 的总权重（键值频率+失败搜索频率）。
实际上，我们可以将失败搜索频率合并到权重中：设 weight[i] 为键值 keys[i] 的频率，failWeight[i] 为失败搜索频率（共 n+1 个）。在区间DP时，总权重 totalWeight(l, r) = sum_{i=l}^{r} weight[i] + sum_{j=l}^{r+1} failWeight[j]。

那么转移方程可写为：

\[ dp[l][r][d] = \min_{m \in [l, r]} \left( dp[l][m-1][d+1] + dp[m+1][r][d+1] + costPerDepth[d] \times totalWeight(l, r) \right) \]

解释：当根节点深度为 d 时，其所有子节点（包括键值和失败搜索）的深度都至少为 d+1，因此整个子树的总代价等于左、右子树的代价（它们的根深度为 d+1）加上根节点本身的贡献：根节点的访问成本（深度 d）乘以整个子树的总权重。这是因为在经典OBST中，当根节点深度增加1时，所有子节点的访问成本都增加一层，所以根节点的成本贡献等于其深度成本乘以子树总权重。
这个公式是经典OBST的推广，其中 costPerDepth[d] 代替了固定的深度增量成本。

  1. 边界条件
    当 l > r 时，表示空子树。此时该子树只有一个失败搜索节点（对应一个空指针），其访问成本基于父节点深度 d（即该空指针的父节点深度为 d），所以：

\[ dp[l][r][d] = costPerDepth[d] \times failWeight[l] \quad (\text{注意：当区间为空时，对应的失败搜索频率是 } failWeight[l]) \]

实际上，当 l > r 时，对应的失败搜索频率是 failWeight[l]（因为区间 [l, r] 为空，即键值区间为空，失败搜索位于位置 l）。但为了统一，我们可以在初始化时处理。

  1. 深度限制
    如果 d > maxDepth，则这个状态非法，代价设为无穷大。

  2. 最终答案
    整个树对应区间 [0, n-1]，根节点深度为 0。所以答案为：

\[ \min_{d=0}^{maxDepth} dp[0][n-1][d] \]

但注意，根节点深度必须从0开始，且不能超过 maxDepth。

逐步计算示例

假设：

  • keys = [10, 20, 30]
  • weight = [3, 1, 4]（键值频率）
  • failWeight = [2, 1, 3, 2]（失败搜索频率，共4个）
  • maxDepth = 2
  • costPerDepth = [1, 2, 4]（深度0、1、2的访问成本）

  1. 计算前缀和 psum 用于快速计算 totalWeight(l, r)：

    • 总权重数组：将 weight 和 failWeight 交错？更简单的方法：直接计算区间总权重。
    • 我们可以预先计算二维数组 wt[l][r] = totalWeight(l, r)。
      例如：wt[0][2] = weight[0]+weight[1]+weight[2] + failWeight[0]+failWeight[1]+failWeight[2]+failWeight[3] = 3+1+4 + 2+1+3+2 = 16。

  2. 初始化 dp[l][r][d] 为无穷大（非法状态）。
    处理空区间 l > r：

    • dp[l][r][d] = costPerDepth[d] * failWeight[l]（对于 l 从0到n，r = l-1）。
      例如：dp[0][-1][0] = costPerDepth[0]*failWeight[0] = 1*2 = 2（区间为空，对应失败搜索在位置0）。

  3. 按区间长度从小到大计算。
    区间长度 len = 1（单个键值）：

    • 例：区间 [0,0]（键值10），枚举深度 d 从0到 maxDepth。
      对于 d=0：枚举根 m=0：
      dp[0][0][0] = dp[0][-1][1] + dp[1][0][1] + costPerDepth[0]*wt[0][0]
      其中 dp[0][-1][1] = costPerDepth[1]*failWeight[0] = 2*2=4，dp[1][0][1] 是空区间（因为 1>0），值为 costPerDepth[1]*failWeight[1]=2*1=2。
      wt[0][0] = weight[0] + failWeight[0]+failWeight[1] = 3+2+1=6。
      所以 dp[0][0][0] = 4 + 2 + 1*6 = 12。
      类似计算其他深度。

  4. 最终计算区间 [0,2]（所有键值）的 dp[0][2][d]，取最小值为答案。

算法复杂度

  • 状态数：O(n^2 * maxDepth)
  • 每个状态转移需要枚举根位置 O(n)
  • 总复杂度：O(n^3 * maxDepth)
  • 可优化：利用决策单调性（Knuth优化）可降为 O(n^2 * maxDepth)，但这里深度维度限制了优化的直接应用。

关键点总结

  • 状态设计要同时涵盖区间、深度，以跟踪节点深度的限制和成本。
  • 转移时，根节点成本贡献等于其深度成本乘以整个子树的总权重（包括键值和失败搜索）。
  • 深度限制通过禁止 d > maxDepth 的状态来实现。
  • 初始条件对应空子树（只有失败搜索节点），其成本由父节点深度决定。

这个扩展问题结合了最优二叉搜索树、深度限制和可变访问成本，是区间DP的一个综合性应用。

区间动态规划例题：最小成本构建唯一二叉搜索树问题（进阶：带深度限制与操作成本） 题目描述 给定一个由 n 个不同整数组成的排序数组 keys （升序），表示二叉搜索树（BST）中所有节点的键值。同时给定一个长度为 n+1 的数组 freq ，其中 freq[i] 表示第 i 个键值（对应 keys[i] ）的搜索频率， freq[n] 表示所有不存在于 keys 中的值的搜索频率（即失败搜索的频率，通常对应叶子节点下的空指针）。 此外，还给出以下限制和成本： 深度限制 ：树中任何节点的深度不能超过一个给定的整数 maxDepth （根节点深度为 0）。 操作成本 ：对每个节点，如果其深度为 d ，则访问该节点的成本为 costPerDepth[d] （一个给定数组，长度为 maxDepth+1 ）。对于失败搜索（即访问空指针），其成本基于其父节点的深度计算（即深度 d 的空指针访问成本为 costPerDepth[d] ）。 目标是构建一棵满足深度限制的二叉搜索树，并最小化以下总代价： \[ \text{总代价} = \sum_ {i=0}^{n-1} \text{freq}[ i] \times (\text{访问键值} \text{keys}[ i] \text{的成本}) + \sum_ {j=0}^{n} \text{freq}[ j ] \times (\text{访问第} j \text{个空指针的成本}) \] 其中访问键值的成本等于其节点深度对应的 costPerDepth 值；访问空指针的成本等于其父节点深度对应的 costPerDepth 值（若父节点深度为 d ）。 解题思路 这是经典最优二叉搜索树（Optimal BST）问题的扩展，增加了深度限制和基于深度的可变访问成本。 核心挑战在于：在构建BST时，不仅要考虑频率加权路径长度，还要确保树不超过最大深度，且节点的访问成本随深度变化。 状态定义 设 dp[l][r][d][k] 表示：用子数组 keys[l..r] （索引从 l 到 r ，包含两端）构建一棵满足深度限制的二叉搜索树，且该树的 根节点深度恰好为 d ，且该树在区间 [l, r] 上构建，同时该树的根节点是区间中的第 k 个元素（即 keys[l + k] 为根， k 从 0 到 r-l ）。 这个状态表示以 keys[l+k] 为根、深度为 d 的BST的最小总代价（包括该子树内所有键值和失败搜索的代价）。 但这样的状态维度太高（ O(n^3 * maxDepth) ），需要优化。 优化状态 观察到：如果我们固定一个区间 [l, r] 和该区间子树的根深度 d ，那么左子树的深度必须为 d+1 ，右子树深度也为 d+1 （因为深度从根向下递增）。因此，我们可以将状态简化为： dp[l][r][d] 表示在区间 [l, r] 上构建一棵BST，且该子树 根节点的深度为 d 的最小总代价（不再显式指定根是哪个键值，而是在状态转移时枚举根的位置）。 状态维度： O(n^2 * maxDepth) 。 转移方程 对于区间 [l, r] 和深度 d ： 如果 l > r ：表示空子树（只有失败搜索）。此时该空子树对应一个空指针，其父节点深度为 d-1 （因为空指针是深度为 d 的节点的子节点，所以其访问成本基于深度 d-1 ？需要仔细定义）。 但更合理的定义是：当区间为空时，表示一个失败搜索节点，其访问成本应由其父节点深度 d 决定（因为该空指针是深度为 d 的节点的子节点，所以访问该空指针的成本为 costPerDepth[d] ）。 因此，若 l > r ，则 dp[l][r][d] = freq[r+1] * costPerDepth[d] ，其中 freq[r+1] 是区间 [l, r] 对应的失败搜索频率（注意：区间 [l, r] 对应失败搜索频率为 freq[l] 到 freq[r+1] ，但当区间为空时，应只对应一个失败搜索节点？需要统一处理频率前缀和）。 为了高效计算总频率，我们预先计算前缀和 psum[i] = sum(freq[0..i]) ，则区间 [l, r] 内所有键值频率和为 psum[r] - psum[l-1] （若 l>r 则为0），且该区间对应的失败搜索频率总和为 psum[r+1] - psum[l] （包括左端和右端的失败搜索）。 但更标准的处理是：对于区间 [l, r] ，其所有节点（键值和失败搜索）的总频率是固定的，等于 psum[r+1] - psum[l] 。 当我们将区间 [l, r] 以某个键值 keys[m] 为根划分为左区间 [l, m-1] 和右区间 [m+1, r] 时，根节点的深度为 d ，访问成本为 costPerDepth[d] 。 左子树根深度为 d+1 ，右子树根深度也为 d+1 。 因此，转移方程为： \[ dp[ l][ r][ d] = \min_ {m \in [ l, r]} \left( dp[ l][ m-1][ d+1] + dp[ m+1][ r][ d+1] + costPerDepth[ d ] \times \text{totalFreq}(l, r) \right) \] 其中 totalFreq(l, r) = psum[r+1] - psum[l] 是该子树中所有键值和失败搜索的总频率。 注意：根节点 keys[m] 的访问频率已包含在 totalFreq 中（因为它是区间的一部分），所以我们只需在总代价中加上 costPerDepth[d] * totalFreq(l, r) 即可（这实际上将根节点的访问成本按频率加权加入，同时左、右子树的代价在递归中已包含各自的频率加权）。 但这个方程有一个问题： costPerDepth[d] * totalFreq(l, r) 实际上将整个区间的总频率都按深度 d 的成本计算了一次，而左、右子树的代价 dp[l][m-1][d+1] 等又已经包含了它们各自的频率按深度 d+1 计算的成本。这会导致重复计算？让我们仔细分析： 更准确的做法是： dp[l][r][d] 应表示该子树的总代价，其中所有节点的访问成本已经根据其自身深度计算。当我们以 keys[m] 为根时： 根节点的深度为 d ，访问成本为 costPerDepth[d] ，频率为 freq[m] （注意 freq[m] 是键值频率，不是失败搜索）。 左子树 [l, m-1] 的所有节点深度在 d+1 及以上，其总代价为 dp[l][m-1][d+1] 。 右子树 [m+1, r] 类似。 此外，还有两个失败搜索节点：一个在左子树空指针（对应频率 freq[m] 的失败部分？实际上失败搜索频率是连续的：区间 [l, r] 对应的失败搜索频率为 freq[l], ..., freq[r+1] ，当我们选择根 m 后，左子树对应失败搜索频率为 freq[l..m] ，右子树对应 freq[m+1..r+1] 。这些失败搜索的访问成本由它们父节点的深度决定，即左子树空指针的父节点深度为 d ，右子树空指针的父节点深度也为 d 。因此，这两个失败搜索节点的成本在根节点层面计算，还是归入左右子树？ 为了简化，我们采用标准最优BST的动态规划方法，但扩展深度和成本： 设 dp[l][r][d] 表示区间 [l, r] 构建的子树，其 根节点的深度为 d ，且该子树的总代价（包括所有键值节点和失败搜索节点）的最小值。 转移时，枚举根节点位置 m ： \[ dp[ l][ r][ d] = \min_ {m \in [ l, r]} \left( dp[ l][ m-1][ d+1] + dp[ m+1][ r][ d+1] + costPerDepth[ d] \times freq[ m ] + \text{额外失败搜索成本} \right) \] 其中 freq[m] 是键值 keys[m] 的频率。 额外失败搜索成本：在根节点 m 处，有两个空指针（左和右），分别对应失败搜索频率 freq[m] 和 freq[m+1] ？不对，失败搜索频率数组 freq 的长度为 n+1 ，索引 i 对应键值 keys[i] 的左空指针（若 i 从0开始）。更标准地： freq[i] 对应在键值 keys[i-1] 和 keys[i] 之间的搜索失败频率（对于 i=0 是小于最小键值的失败搜索，对于 i=n 是大于最大键值的失败搜索）。 为了避免混淆，我们采用经典OBST的DP定义，但加上深度维度。 令 w(l, r) = sum_{i=l}^{r} freq[i] + sum_{j=l}^{r+1} failFreq[j] 是区间 [l, r] 的总权重（键值频率+失败搜索频率）。 实际上，我们可以将失败搜索频率合并到权重中：设 weight[i] 为键值 keys[i] 的频率， failWeight[i] 为失败搜索频率（共 n+1 个）。在区间DP时，总权重 totalWeight(l, r) = sum_{i=l}^{r} weight[i] + sum_{j=l}^{r+1} failWeight[j] 。 那么转移方程可写为： \[ dp[ l][ r][ d] = \min_ {m \in [ l, r]} \left( dp[ l][ m-1][ d+1] + dp[ m+1][ r][ d+1] + costPerDepth[ d ] \times totalWeight(l, r) \right) \] 解释：当根节点深度为 d 时，其所有子节点（包括键值和失败搜索）的深度都至少为 d+1 ，因此整个子树的总代价等于左、右子树的代价（它们的根深度为 d+1 ）加上根节点本身的贡献：根节点的访问成本（深度 d ）乘以整个子树的总权重。这是因为在经典OBST中，当根节点深度增加1时，所有子节点的访问成本都增加一层，所以根节点的成本贡献等于其深度成本乘以子树总权重。 这个公式是经典OBST的推广，其中 costPerDepth[d] 代替了固定的深度增量成本。 边界条件 当 l > r 时，表示空子树。此时该子树只有一个失败搜索节点（对应一个空指针），其访问成本基于父节点深度 d （即该空指针的父节点深度为 d ），所以： \[ dp[ l][ r][ d] = costPerDepth[ d] \times failWeight[ l] \quad (\text{注意：当区间为空时，对应的失败搜索频率是 } failWeight[ l ]) \] 实际上，当 l > r 时，对应的失败搜索频率是 failWeight[l] （因为区间 [l, r] 为空，即键值区间为空，失败搜索位于位置 l ）。但为了统一，我们可以在初始化时处理。 深度限制 如果 d > maxDepth ，则这个状态非法，代价设为无穷大。 最终答案 整个树对应区间 [0, n-1] ，根节点深度为 0。所以答案为： \[ \min_ {d=0}^{maxDepth} dp[ 0][ n-1][ d ] \] 但注意，根节点深度必须从0开始，且不能超过 maxDepth 。 逐步计算示例 假设： keys = [10, 20, 30] weight = [3, 1, 4] （键值频率） failWeight = [2, 1, 3, 2] （失败搜索频率，共4个） maxDepth = 2 costPerDepth = [1, 2, 4] （深度0、1、2的访问成本） 计算前缀和 psum 用于快速计算 totalWeight(l, r) ： 总权重数组：将 weight 和 failWeight 交错？更简单的方法：直接计算区间总权重。 我们可以预先计算二维数组 wt[l][r] = totalWeight(l, r) 。 例如： wt[0][2] = weight[0]+weight[1]+weight[2] + failWeight[0]+failWeight[1]+failWeight[2]+failWeight[3] = 3+1+4 + 2+1+3+2 = 16 。 初始化 dp[l][r][d] 为无穷大（非法状态）。 处理空区间 l > r ： dp[l][r][d] = costPerDepth[d] * failWeight[l] （对于 l 从0到n， r = l-1 ）。 例如： dp[0][-1][0] = costPerDepth[0]*failWeight[0] = 1*2 = 2 （区间为空，对应失败搜索在位置0）。 按区间长度从小到大计算。 区间长度 len = 1 （单个键值）： 例：区间 [0,0] （键值10），枚举深度 d 从0到 maxDepth 。 对于 d=0 ：枚举根 m=0 ： dp[0][0][0] = dp[0][-1][1] + dp[1][0][1] + costPerDepth[0]*wt[0][0] 其中 dp[0][-1][1] = costPerDepth[1]*failWeight[0] = 2*2=4 ， dp[1][0][1] 是空区间（因为 1>0 ），值为 costPerDepth[1]*failWeight[1]=2*1=2 。 wt[0][0] = weight[0] + failWeight[0]+failWeight[1] = 3+2+1=6 。 所以 dp[0][0][0] = 4 + 2 + 1*6 = 12 。 类似计算其他深度。 最终计算区间 [0,2] （所有键值）的 dp[0][2][d] ，取最小值为答案。 算法复杂度 状态数： O(n^2 * maxDepth) 每个状态转移需要枚举根位置 O(n) 总复杂度： O(n^3 * maxDepth) 可优化：利用决策单调性（Knuth优化）可降为 O(n^2 * maxDepth) ，但这里深度维度限制了优化的直接应用。 关键点总结 状态设计要同时涵盖区间、深度，以跟踪节点深度的限制和成本。 转移时，根节点成本贡献等于其深度成本乘以整个子树的总权重（包括键值和失败搜索）。 深度限制通过禁止 d > maxDepth 的状态来实现。 初始条件对应空子树（只有失败搜索节点），其成本由父节点深度决定。 这个扩展问题结合了最优二叉搜索树、深度限制和可变访问成本，是区间DP的一个综合性应用。