PTA上这道“7-3 最优二叉搜索树”我印象很深。当年刷题的时候我在这道题上卡了挺久倒不是题目本身的代码量有多大而是“凭什么这么递推”这个问题一直没想透。后来静下心把状态转移方程在草稿纸上画了十几遍才算是真正吃透了。这篇文章我就把当时的思考过程、代码写法、还有踩过的坑一次性讲清楚。不管你是正在刷《算法导论》的在校生还是考前突击PTA题集的老哥看完这篇应该都能直接AC。先简单交代一下这个问题的应用背景。最优二叉搜索树Optimal Binary Search Tree简称OBST说的是这么一件事你有一组有序的键值比如词典里的单词每个键有固定的被查找概率。现在要构造一棵二叉搜索树让查找的期望比较次数最少。注意这里每个键本身有权重而不像哈夫曼树那样只关心叶子。换句话说如果一个键特别常被访问最好让它靠近根如果一个键几乎不会被访问哪怕挂得很深也无所谓。这个优化问题动态规划就是标准解法。1. 题目理解与问题建模1.1 先搞清楚题目在问什么PTA这道题通常会先给你一个 n表示键的个数然后给 n 个概率值代表每个键被查询的概率。注意这些概率加起来不一定等于1可能只是“访问频度”或者“权重”题目一般会说明。你要求的是构造一棵二叉搜索树使得查找这 n 个键的期望代价最小输出这个最小代价。这个“期望代价”怎么计算按标准定义每个键的查找代价等于它的深度加一根节点深度为0访问到根要做1次比较。整棵树的期望查找代价就是所有概率 * 深度1的累加。如果一棵树选得不合适访问频率高的键待在叶子位置期望代价就会暴涨反过来把热门的键挂在根附近代价就小。我当年犯过的一个理解性错误是——以为往每个键上套平衡二叉树的思路就能解决也就是让树尽量“矮”。平衡确实能减少最坏查找长度但平衡树没有考虑概率分布。想想看如果某个键被查的概率占90%那哪怕整棵树歪成一条链只要它挂在根上期望代价也就是 0.9*1 其他一些零头大概率比一棵高度只有3但把热门键埋在深处的平衡树要好。OBST比平衡树多考虑了“概率”这个维度所以结果通常不是平衡的。1.2 从“区间”的角度看这棵树为了用动态规划你首先要接受一个关键事实在最优二叉搜索树里任意一棵子树它的键在原始序列里一定是连续的。这句话怎么理解二叉搜索树有一个“中序遍历有序”的性质任意取一个节点作为根它的左子树里所有键都小于它右子树里所有键都大于它。那么如果整棵树的键是 k1 k2 ... kn某棵子树包含的键必然构成这段有序序列里的一个连续子串。举例来说假设键是 1, 2, 3, 4, 5某个节点取值为3那么它的左子树只可能是由 {1,2} 组成或者其中一部分不可能出现 {1,4} 这种跳跃的组合。因为如果左子树同时包含1和4那4比3大按BST规则它绝不可能在3的左子树里。这个性质极其重要——它把一棵树的搜索空间压缩成了“区间套区间”的结构这正是区间动态规划能下手的地方。有了这个性质问题就变成了给一个键区间 [i, j]在这个区间内选一个键 k 当根把左边 [i, k-1] 和右边 [k1, j] 分别构造成最优子树。于是问题天然有了“最优子结构”。1.3 为什么不能贪心我见过有同学偷懒想直接选概率最大的当根然后递归处理左右两边。这个思路在很多情况下能蒙对但它不是正确解法。原因在于选根这件事影响的不只是根本身的代价还会让左右子树里每一个节点的深度都加1也就是说概率大的键虽然被放到了根但如果左右子树整体代价抬升过多反而得不偿失。用一个极简例子说明键A概率0.4键B概率0.3键C概率0.3。贪心选A当根左右两边分别是B和C总代价是 0.4*1 0.3*2 0.3*2 1.6。但选B当根左子树空右子树为A、C如果右子树选A当根C是A的右孩子总代价是 0.3*1 0.4*2 0.3*3 2.0。贪心更好。但换一组概率比如A概率0.1B概率0.8C概率0.1贪心选B当根总代价 0.8*1 0.1*2 0.1*2 1.2这个没问题。那如果A概率0.35B概率0.3C概率0.35呢贪心选A当根总代价 0.35*1 0.3*2 0.35*2 1.65但如果选B当根A在左C在右总代价 0.3*1 0.35*2 0.35*2 1.7依然贪心好。光看这几个例子看不出问题但你只要构造一组概率差得悬殊的组合比如A概率0.2B概率0.19C概率0.61贪心选C当根0.61*1 0.2*2 0.19*2 1.39。选A当根呢左空右子树由B、C组成如果右子树选C当根B是C左孩子总代价 0.2*1 0.61*2 0.19*3 1.99明显更差。贪心此时是对的。到目前为止贪心都赢是不是可以用贪心不是。关键在于“根的选择会影响子树深度”这种全局联动效应在概率分布更复杂时一定会出现贪心失效的情况。严格证明不做展开但你只要记住直接选最大概率当根不能保证子树部分也是全局最优。动态规划的价值就在于枚举每一个当根的可能而不是一拍脑袋选最大。2. 动态规划推导与状态设计2.1 状态定义和递推式这道题的状态定义其实很直观。设dp[i][j]表示只考虑键 i 到键 j 这一段连续区间构造一棵最优二叉搜索树时它的最小期望查找代价。注意一个细节这里的“期望查找代价”只统计区间内所有键的代价不含区间外的东西。这样定义是为了方便区间合并时做加法。假设我们在区间 [i, j] 里选 k 当根节点。那么左右子树分别是 [i, k-1] 和 [k1, j]。整棵树的期望代价怎么算根 k 自己的代价是p[k] * 1。左子树和右子树里每个节点的深度都比原来的子树根深度多1所以每一个键的代价整体增加一次自身概率。这就引出了递推式dp[i][j] min( dp[i][k-1] dp[k1][j] sum(i, j) )对 k 从 i 到 j 取最小。其中sum(i,j)是第 i 到第 j 个键的概率之和。我看到很多初学者不理解为什么最后要加sum(i,j)。这里我说个最直白的解释你把左右子树各自的最优结构搬上来以后由于多了根节点左子树和右子树里所有键的深度都增加了1。深度每增加1查找代价就增加该键概率的1倍。把区间里所有键的“深度增加1”带来的额外代价加起来正是所有概率之和sum(i,j)。你可以反过来验证如果区间长度为1即只有一个键此时 k 只能等于 i。dp[i][i] dp[i][i-1] dp[i1][i] sum(i,i)。我们把空树的 dp 定义成0于是dp[i][i] p[i]正好对应单个节点、根深度0、查找比较次数1代价p[i]*1。这个基础情况很关键后面代码里初始化要用到。2.2 空树的处理dp[i][i-1] 是什么上面提到了dp[i][i-1]这就是“空区间”的代价。按常理空树没有任何节点查找代价就是0。但代码层面这个状态必须能被访问到才行。比如递推dp[i][i]时要访问dp[i][i-1]和dp[i1][i]递推dp[1][3]并且 k1 时要访问dp[1][0]和dp[2][3]。因此数组要开得比 n 大一些并把边界外的位置也初始化为0。我最早写代码的时候直接开dp[1005][1005]然后只在dp[i][i]p[i]的时候顺手把边界清成0结果 k 循环到边界时访问到的是未初始化的脏数据答案全乱。后来我统一先把整个 dp 数组清零再把对角线设成p[i]就稳了。很多人觉得初始化很简单但这一块恰恰是OBST代码里最容易出隐晦 bug 的地方。2.3 为什么区间长度要从小到大动态规划的核心是“用小问题的答案组装大问题的答案”。计算dp[i][j]时需要用到dp[i][k-1]和dp[k1][j]这两个区间的长度都小于j-i1。所以只要我按照区间长度从1到n、区间起点从小到大依次计算就能保证算到大区间时所有子区间都已经算好了。这就像盖楼你必须从1层盖到2层再盖到3层不能反过来。有些同学写成从 i 到 j 的顺序直接三重循环结果算dp[1][5]的时候dp[2][5]还没算出来拿到的就是0或者垃圾值导致答案完全不对。这是动态规划题目里特别常见的“依赖顺序”坑。2.4 复杂度分析时间复杂度区间数量是 O(n^2)每个区间要枚举 k枚举总数 O(n)所以整体是 O(n^3)。空间复杂度一个二维 dp 数组O(n^2)。在 PTA 这类题目里n 一般不会大得离谱几十到几百之间这个复杂度完全能扛得住。如果 n 到 1000O(n^3) 会到 10 亿次循环C语言勉强能跑但多了就不行了。这就引出了 Knuth 优化——不过 PTA 基础题一般不要求后面扩展部分我会提一下。3. 代码实现与逐步拆解3.1 基础框架读入和前缀和这类题目通常是单组测试数据。第一行读入 n第二行读入 n 个浮点数。有些题目会把概率写成整数频度注意按需读成double还是int。为了后面快速求sum(i,j)我们预处理一个前缀和数组double sum[MAXN]; for (int i 1; i n; i) { sum[i] sum[i - 1] p[i]; }这样sum(i,j) sum[j] - sum[i-1]求区间和就是 O(1)。如果不做前缀和每次在 k 循环里临时累加复杂度会变成 O(n^4)能过纯属侥幸。3.2 dp数组初始化和主循环核心代码不长我直接贴出来并标好每一步在干什么#include stdio.h #define MAXN 105 #define INF 0x3f3f3f3f double p[MAXN]; double dp[MAXN][MAXN]; double sum[MAXN]; int main() { int n; while (scanf(%d, n) ! EOF) { for (int i 1; i n; i) { scanf(%lf, p[i]); sum[i] sum[i - 1] p[i]; } // 初始化所有状态先置0空区间代价为0 for (int i 0; i n 1; i) { for (int j 0; j n 1; j) { dp[i][j] 0; } } // 长度1的区间单节点树代价就是该键的概率 for (int i 1; i n; i) { dp[i][i] p[i]; } // len: 区间长度从2开始枚举 for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; dp[i][j] INF; double w sum[j] - sum[i - 1]; // 枚举根节点 k for (int k i; k j; k) { double temp dp[i][k - 1] dp[k 1][j] w; if (temp dp[i][j]) { dp[i][j] temp; } } } } printf(%.2lf\n, dp[1][n]); } return 0; }注意我用了while (scanf(%d, n) ! EOF)因为PTA有些题是多重测试用这个写法能兼容单组和多组两种情况不会WA。如果你确定只有一组输入直接scanf一次也没问题但养成这个习惯总没错。3.3 浮点数的比较问题这段代码里double的比较直接用了。有人担心浮点数精度问题但这里所有值都是加法和初始化出来的不涉及除法或大量截断误差直接用是没有问题的。如果你实在不放心可以写temp 1e-9 dp[i][j]但没必要。输出格式看题目要求一般是保留两位小数用printf(%.2lf\n, ...)即可。注意别漏了\nPTA对格式检查很严少了换行直接给你判格式错误。3.4 如果不只求代价还要求输出树形结构有一部分OBST的题目不止要求输出最小期望代价还会让你输出先序遍历的根节点序列或者输出以某种方式表示的树。这就要额外记录root[i][j]。方法很简单在dp[i][j]被更新时同步记录root[i][j] k。基础情况dp[i][i]时root[i][i] i。最后用递归输出void dfs(int left, int right) { if (left right) return; int k root[left][right]; printf(%d , k); // 先序输出根 dfs(left, k - 1); dfs(k 1, right); }如果题目要求的是后序或者层序把这个递归顺序改一下就行。核心是先初始化好root数组再在每次更新 dp 时同步更新根记录。我见过同学忘记初始化root[i][i]i结果单节点区间输出0最后没几个AC的。4. 常见错误与调试技巧4.1 数组下标越界看不见的杀手OBST 的下标设计有一个天然难点dp[i][k-1]和dp[k1][j]里k 可以等于 i也可以等于 j。这意味着你会访问到dp[i][i-1]和dp[j1][j]。这些是合法的“空区间”算出来应该为0。但如果你数组只开[n1][n1]当 i1、k1 时dp[1][0]其实在C语言数组边界内不会段错误但内容是否安全就看你有没有初始化。更危险的是dp[k1][j]当 kj 时访问dp[j1][j]数组第二维越界到 j1。如果你只开MAXN100n 又是100这里就可能访问到dp[101][100]属于越界但没崩的未定义行为。所以我强烈建议数组开到MAXN105并且在初始化时把0到n1全部清零保证这些“越界但不越太多”的位置有确定值。4.2 三重循环的边界条件写错写区间DP时最经典的边界就是i len - 1 n。有些同学喜欢写i n或者j n但忘记控制 len结果j跑到 n 以后数组越界。更隐蔽的错误是外层 len 从1开始然后内层还把长度为1的情况再算一遍覆盖掉刚才的初始化也不报错但万一你循环里写的是dp[i][i-1] dp[i1][i] w而 w 等于p[i]那结果还是对的白计算了一遍浪费但不致命。4.3 概率加起来的“和”要重新计算在递推式里w sum[j] - sum[i-1]是“区间总概率”。每次进入一个新的[i,j]区间都要重新求一次因为它和 k 无关可以提前算出来不用放进 k 循环里。但如果把它算成sum[n]也就是总概率那就错了。因为左右子树的深度增加只影响当前区间 [i,j] 里的键区间外的键根本不在当前子树里它们是否增加深度由更高层的递归决定。你要是把总概率加进去每个子树都给自己加一层全体的概率最后答案会大得离谱。4.4 一个问题KEY是整型权重怎么办有的题给的不是浮点概率而是整数访问次数。例如输入 n3键的访问次数分别是 5、3、8。这时候你可以直接把访问次数当作权重算出来的“期望代价”实际上是“总比较次数”不是真正的概率期望。递推式完全不用改把double改成int即可。唯一要注意的是 INF 要开成足够大的整数比如0x3f3f3f3f。用int时dp初始化和运算都比double快一点但思路没区别。4.5 实测调试心得我当年在PTA上第一次交这个题WA了三次。第一次错在没初始化数组第二次错在把w放到了 k 循环里重复累加第三次错在读入时没处理多组数据。后来我在代码里加了几个printf检查中间结果专门打印长度为1、2、3的dp值和手算的答案对了一遍才确定递推写对了。建议你也这么做。手动构造一个小数据比如3 0.2 0.3 0.5手算如果根是3左子树为1、2代价 0.5*1 dp[1][2] (0.20.3)而dp[1][2] min(0.2*1 0.3*2, 0.3*1 0.2*2) min(0.8, 0.7) 0.7所以总代价 0.5 0.7 0.5 1.7。如果根是2左右子各一个代价 0.3*1 0.2*2 0.5*2 1.7。如果根是1代价 0.2*1 dp[2][3] 0.8而dp[2][3] min(0.3*10.5*2, 0.5*10.3*2) 1.1所以总代价 0.2 1.1 0.8 2.1。最小值就是1.7。你用代码跑一下如果答案不是1.70说明初始化或者循环顺序有 bug对照这个手算过程很容易定位。5. 变式题目与进阶优化5.1 带“虚键”的最优二叉搜索树教科书版本里还有一个扩展把查找失败的情况也考虑进来。比如你要在一个词典里查单词查不到的时候也会有一个“失败代价”。这些失败查找会落在 BST 的空指针上也就是叶子下面对应一组“虚键”dummy key。如果在OBST问题里加了虚键递推式要调整为除了枚举真实键作为根还要枚举空子树作为叶子而 dp 状态会从[i,j]扩展到[i,j]加上两个虚拟键边界。也就是说需要把真实键和失败键放在一条序列上交错处理。PTA基础题很少考这个但《算法导论》和考研题里会出现。理解了不加虚键的版本加虚键只是把sum的范围和下标处理多处理一层难度没有本质提升。5.2 键值无序怎么办题目如果故意不给有序键而是给你几个键和它们的访问概率那你第一步一定是按键值大小排序同时让概率跟着对应键走。因为 BST 要求中序有序排序后的下标区间才满足“子树键连续”的性质。如果键本来就是 1 到 n 的整数这一步就省了。但排序之后p[i]要和键绑定一起移动不能只排概率否则就错乱了。这个细节我在其他题解里见过有人踩坑。5.3 Knuth 优化把 O(n^3) 降到 O(n^2)如果你追求极致性能可以了解一下四边形不等式优化也叫 Knuth 优化。它利用了单调性最优根的位置root[i][j]满足root[i][j-1] root[i][j] root[i1][j]。这样一来在枚举 k 的时候不用从 i 扫到 j只需要扫root[i][j-1]到root[i1][j]这一段平均总复杂度降到 O(n^2)。不过这个优化不是无脑套的它要求 DP 满足四边形不等式而 OBST 恰好满足。PTA 的题目数据量如果不是1000以上没必要上这个优化代码还容易写错。我建议先把朴素版吃透优化可以作为进阶练习。5.4 与哈夫曼树的对比很多同学会把 OBST 和哈夫曼树搞混因为两者都处理“带权键值”的树结构。这里我做一个对比对比维度最优二叉搜索树哈夫曼树键的存放位置所有节点都存键内部节点和叶子都是真实键所有键都在叶子节点内部节点只是合并节点中序性质必须满足BST的中序有序性没有有序性要求构造目标最小化查找每个键的期望比较次数最小化带权路径长度常用于编码适用场景静态字典、缓存索引、数据库检索压缩编码、文件打包一句话概括哈夫曼树关心的是所有叶子深度乘以权重OBST关心的是每个节点的查找概率。OBST 的“子树键连续”性质在哈夫曼树里是完全不存在的所以两者的 DP 模型完全不同。6. 实战经验总结与后续扩展PTA 的“7-3 最优二叉搜索树”是我见过最能体现“区间DP”思想的一道入门题。它的代码量小但思维量集中往后你学矩阵连乘、石子合并、多边形剖分会发现它们共享同一套分析套路定义状态、确定依赖关系、按区间长度从小到大枚举。OBST是这套思路的最佳练手题。这里再把我个人的几个实操习惯分享出来第一任何区间DP先把dp数组和root数组的初始化做干净尤其是空区间状态。不要觉得这是小事越复杂的题初始化带来的 bug 越难排查。第二写三重循环时把i len - 1 n这个条件直接写在for里不要写在循环体里用if跳过逻辑更清晰。第三如果题目要求输出树结构一定记得用root数组记录而不是在算完dp之后再重新“猜”哪一个是根那个过程极其容易出错。我在刷题的时候还想明白了一件事这类题目不是考你能不能背下递推式而是考你“为什么这个状态是对的”。只要想清楚“子树键连续”“空树代价为0”“所有节点深度加1所以加上区间概率和”这三个关键点你就再也不会忘记递推式。后续如果你想深挖可以试着用OBST做一个小型单词查找程序。定义一组长单词列表统计每个单词在文本中的出现频率作为概率再用OBST构建索引对比一下顺序查找、二分查找和OBST的期望比较次数会很直观地看出OBST的优势。这个扩展练习比单纯刷题有意思得多也能让你把DP模型迁移到实际问题里。最后再提一个细节有的PTA版本题目会要求输出“根节点编号”的先序序列有的只要求输出最小平均查找次数。拿到题目先看清楚输出格式读题不仔细的话代码对了也可能因为输出格式或者精度位数被判错。好在这道题的代码结构固定确认好需求后照着上面的框架改一改AC问题不大。