最优二叉搜索树这道题在PTA上一出现基本就是算法设计与分析课程的“劝退题”。它没有现成的遍历模板可以套核心是要把动态规划的递推式真正搞明白再小心处理矩阵输出。我最初在PTA上刷7-3时代码跑不对的原因集中在三个地方状态初始化不对、区间枚举顺序反了、输出格式跟题面样例对不上。这篇文章不搞“贴个AC代码就跑”那一套而是把建模、递推推导、C语言实现、样例验证四个环节完整过一遍读完你可以做到既会写代码也能给别人讲清楚为什么这么写。下面按最常见的PTA版本讲给定n个互不相同的关键字x1 x2 ... xn以及每个关键字的搜索概率pi正实数要求构造一棵最优二叉搜索树使得查找成功时的期望比较次数最小并输出动态规划过程中的W、C、R三个矩阵。如果你拿到的题面还带搜索失败概率q[]也就是教材里说的“虚键”版本也不用慌递推式大体一致我后面会单独说明差异。1. 先看题目本质这不是让你“建一棵树”而是让你“选一棵树”1.1 题目输入输出背后的信息量题目输入通常只有两行第一行是n第二行是n个概率。信息量不大但仔细读能读出几个关键约束关键字序列严格递增这是二叉搜索树的天然性质也意味着中序遍历序列被固定了。不管树形怎么变每个结点的左右位置关系都要满足有序性。概率是正实数可能是整数也可能是0.1、0.15这种小数所以读入和处理都要按浮点数来。输出不只是最后的最优代价很多版本还要求输出三个矩阵W[i][j]区间概率和、C[i][j]最优期望代价、R[i][j]最优根下标。“中序遍历固定”这个话题值得多说一句。给定一组有序关键字能构造出多少棵不同的二叉搜索树答案是卡特兰数。比如n5时是42棵n10时是16796棵n20时已经是6564120420这种量级。所以题目本质上不是让你从零“建树”而是在所有可能的树形中“选一棵”代价最小的。每个区间[i, j]选择谁当根就唯一决定了一棵子树的结构最后拼出整棵树。1.2 读题时容易忽略的细节点我在PTA上见过不少同学包括当年的我因为下面的细节反复提交下标从1开始还是从0开始。建议统一从1开始这样空区间可以表示为[i, i-1]或者[j1, j]判断和初始化都方便。空子树的代价。当区间左端点大于右端点时表示没有结点代价是0。这在递推中会反复用到。输出保留几位小数。很多版本要求两位小数用%.2f也有要求四位或六位的必须看题面。多个最优解取哪个根。有些题目会明确说“如果存在多个最优解输出编号较小的根”没说的话按第一个找到的最优k处理即可。这几个点看起来小但每一个都直接决定你是否能AC。尤其是最后一个如果题目对R矩阵有要求平局处理不一致会导致矩阵输出跟样例对不上一查一个准。2. 为什么“每次让最大概率当根”救不了你2.1 一个三节点反例很多人第一反应是谁被搜得多谁就该当根这不就是贪心吗我们用一个三结点例子把它否决掉。假设三个关键字x1、x2、x3概率分别是p10.3、p20.3、p30.4。概率最大的是x3按照贪心思路把x3放根上。剩下x1、x2在左子树。左子树有两种挂法左子树根x1x2是x1的右孩子。整棵树深度x3在深度1x1在深度2x2在深度3。期望代价 0.4×1 0.3×2 0.3×3 1.9。左子树根x2x1是x2的左孩子。整棵树深度x3在深度1x2在深度2x1在深度3。期望代价 0.4×1 0.3×2 0.3×3 1.9。所以不管左子树怎么排贪心版本的代价都是1.9。但如果让x2当根x1挂左、x3挂右深度分别是x2深度1x1深度2x3深度2。期望代价 0.3×1 0.3×2 0.4×2 1.7。1.7 1.9贪心输了。这个例子很能说明问题概率最大的x3当根只省下了自己那一层却把两个0.3概率的结点压到了深度2和深度3让x2当根x3虽然从深度1变成深度2只是多付出0.4但x1保持深度2x2本身也只深度1。根的选择会影响整棵子树所有结点的深度这是一种全局连锁局部最优根本顶不住。2.2 最优子结构与重叠子问题既然贪心不行那就要枚举。枚举的核心观察是一旦选定根k左子树[i, k-1]和右子树[k1, j]各自的最优结构是独立的互不影响。这就满足动态规划的最优子结构。另一个特征是重叠子问题。比如要算c[1][5]枚举根时会反复用到c[2][4]、c[3][4]等子区间而要算c[2][4]又要用到更小的区间。同一个子问题被不同的上层问题重复求解如果直接递归代价是卡特兰数级别的。用一张二维表把每个区间的最优值存下来每个区间只算一次总复杂度就从指数级降到O(n^3)。顺带说一句很多人会拿OBST和哈夫曼树做对比。两者确实都在给带权结点排队但哈夫曼树把所有数据都放在叶子且不要求中序遍历有序OBST的所有关键字都在内部结点且必须保持二叉搜索树的有序性。理解这个区别后面看优化方向会清楚很多。3. 递推式的建立一次“深度下沉”的思想实验3.1 先定义清楚c[i][j]表示什么在写代码之前务必将状态定义刻在脑子里w[i][j]区间[i, j]内所有概率之和即sum_{ti}^{j} p[t]。c[i][j]由关键字x[i..j]构成的最优二叉搜索树在“子树根深度为1”的度量下查找成功时的最小期望比较次数。r[i][j]达到最优值时的根下标k。“子树根深度为1”这个定义很重要。查找一个深度为d的结点需要比较d次命中根节点只需要比较1次所以根的贡献就是p[k]×1。3.2 从“把子树挂到根下面”推导转移方程假设区间[i, j]选择k作为根。先单独看左子树[i, k-1]。这棵子树内部的最优期望代价是c[i][k-1]但这个值是在“左子树根深度为1”的前提下算出来的。现在左子树被挂到k的左边实际深度整体下沉一层左子树里每个结点的比较次数都要加1。左子树所有结点的概率之和是w[i][k-1]所以左子树真实贡献变成c[i][k-1] w[i][k-1]同理右子树真实贡献是c[k1][j] w[k1][j]根k本身的贡献是p[k]。三者相加total p[k] c[i][k-1] w[i][k-1] c[k1][j] w[k1][j]把w和p并在一起看p[k] w[i][k-1] w[k1][j] w[i][j]因为w[i][j]定义就是整个区间所有概率之和。于是得到最简形式c[i][j] w[i][j] min_{i≤k≤j}(c[i][k-1] c[k1][j])这个式子就是整道题的核心。很多同学背下来了但不知道“深度下沉”那一层含义遇到带虚键的变形就懵了。其实只要记住“子树挂到根下面深度加1代价增加w”什么变形都能推。3.3 边界条件空子树代价为零当i j时区间没有关键字期望代价为0。代码里C数组是全局变量默认就是0所以不需要特别初始化。单点区间[i, i]也不需要特殊处理用递推式算一遍c[i][i] w[i][i] min(c[i][i-1] c[i1][i]) p[i] 0 p[i]正好等于单结点树的期望代价。这说明递推式对长度为1的区间也自洽。w[i][j]则建议用前缀和计算定义sumP[t] sum_{s1}^{t} p[s]则w[i][j] sumP[j] - sumP[i-1]。这样在任何地方取w都是O(1)不会额外增加复杂度。4. 用C语言实现从递推式到可运行代码4.1 数据结构、输入与初始化n的范围一般是50以内数组开到55就足够。注意C数组在访问c[i][k-1]时k-1可能等于i-1最小为0在访问c[k1][j]时k1可能等于j1最大为n1所以数组第二维至少开到n2。#include stdio.h #define MAXN 55 #define INF 1e18 double p[MAXN]; double sumP[MAXN]; double w[MAXN][MAXN]; double c[MAXN][MAXN]; int r[MAXN][MAXN]; int n;读入部分scanf(%d, n); for (int i 1; i n; i) { scanf(%lf, p[i]); sumP[i] sumP[i - 1] p[i]; }随后预处理w矩阵。w[i][j]只在j i时有效其他位置保持0即可for (int i 1; i n; i) { for (int j i; j n; j) { w[i][j] sumP[j] - sumP[i - 1]; } }单点区间可以直接初始化也可以交给后面的递推二选一。为了减少出错的环节我更推荐把它交给递推统一处理这样少一段代码少一个地方出错。但很多教材版代码里会先写一句c[i][i] p[i]也完全没问题只要保证后面不重复覆盖。4.2 区间DP的循环顺序为什么要按长度递增主循环务必按区间长度从小到大算。当你在算长度len的区间时会访问长度小于len的c[i][k-1]和c[k1][j]这些值必须在之前已经算好。最不容易绕晕的写法是for (int len 1; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; double best INF; int bestK i; for (int k i; k j; k) { double val c[i][k - 1] c[k 1][j]; if (val best) { best val; bestK k; } } c[i][j] best w[i][j]; r[i][j] bestK; } }这里len从1开始是因为递推式对单点区间自洽len1时会算出c[i][i] p[i]。这种写法在初始化上最省心也不用担心漏掉哪个单点。有人喜欢写for (int i n; i 1; i--)再从j i开始本质上也是保证子区间更短但容易下标绕晕。我建议新手一律用长度递增直观且不容易错。4.3 矩阵输出与递归还原最优树如果题目要求输出W、C、R三个矩阵通常以“上三角”形式输出。下面是一种典型写法每个数值占7.2f的宽度空位用空格填充for (int i 1; i n; i) { for (int j 1; j n; j) { if (j i) { printf( ); } else { printf(%7.2f, w[i][j]); } } printf(\n); }C矩阵同理把w换成c。R矩阵是整数格式改为%6dfor (int i 1; i n; i) { for (int j 1; j n; j) { if (j i) { printf( ); } else { printf(%6d, r[i][j]); } } printf(\n); }如果题目要求输出最优树结构利用R矩阵可以递归还原。R[1][n]是整棵树的根然后递归处理左右子树先序遍历就是void printTree(int i, int j) { if (i j) { return; } int k r[i][j]; printf(%d , k); printTree(i, k - 1); printTree(k 1, j); }把这三段组合起来补上main函数框架就是一份完整的AC代码。完整可运行的代码我在文末给一个整理版方便直接对照。5. 样例验证与踩坑复盘5.1 手推一个三节点样例用2.1那个反例做验证p {0.3, 0.3, 0.4}。先算所有ww[1][1] 0.3w[2][2] 0.3w[3][3] 0.4w[1][2] 0.6w[2][3] 0.7w[1][3] 1.0len 1时c[1][1] 0.3r[1][1] 1c[2][2] 0.3r[2][2] 2c[3][3] 0.4r[3][3] 3len 2时区间[1,2]k1时val c[1][0] c[2][2] 0.3k2时val c[1][1] c[3][2] 0.3。两者都是0.3加w[1][2]0.6得到c[1][2]0.9。按“第一个最优k”原则r[1][2]1。区间[2,3]k2时val c[2][1] c[3][3] 0.4k3时val c[2][2] c[4][3] 0.3。取较小的0.3加w[2][3]0.7得到c[2][3]1.0r[2][3]3。len 3时区间[1,3]k1c[1][0] c[2][3] 0 1.0 1.0k2c[1][1] c[3][3] 0.3 0.4 0.7k3c[1][2] c[4][3] 0.9 0 0.9最小值是0.7取k2。加w[1][3]1.0得到c[1][3]1.7r[1][3]2。跟前面手算的1.7完全对上了。用R矩阵还原树整树根是2左区间[1,1]的根是1右区间[3,3]的根是3先序序列是2 1 3结构就是x2在根、x1在左、x3在右。5.2 输出格式的隐坑空格、占位符与矩阵对齐输出格式是这道题最容易无缘无故扣分的地方。很多PTA题目的矩阵输出对占位符宽度有严格要求%7.2f和%6d是我个人比较常用的组合但它不一定匹配你的题面。务必以题目给的“输出样例”为准样例里一位整数占几个空格你就用几个宽度样例空位用什么填充你就用什么填充。最稳妥的方法是把样例输出下载下来自己程序跑一遍后逐字符比对尤其是行末有没有多余空格、空位是0还是空白。如果题目要求输出完整n×n矩阵而不是上三角把else分支去掉改成统一输出即可。注意此时j i的区域到底补0.00还是留空题面通常会写明。5.3 我在调试中遇到的三个典型bug这三个bug都是实际调过、翻过车的列出来给大家避坑。第一单点区间初始化遗漏。如果采用“先初始化c[i][i] p[i]”的写法有一项漏掉会导致后面所有依赖它的区间计算结果偏小而且偏小的数值特别隐蔽你不容易看出是哪里错了。反过来如果用len从1开始的统一递推写法就不会有这个风险。第二INF设置过小。概率虽然是小数但如果题目给出的概率数值很大或者你选择的权值单位不同1e9这种规模可能会被真实答案逼近。稳妥做法是直接给1e18反正double溢出不了。第三平局根的选择不一致。如果题面要求“多个最优解输出编号最小的根”那么更新条件应该用if (val best - 1e-9)只有严格小于才更新如果要求编号最大的根用if (val best 1e-9)更新。这里引入1e-9容差是为了避免浮点误差导致平局判定错误。还有一个小细节题目如果没说平局规则一般以第一个k为准即if (val best)。6. 进阶四边形不等式优化与OBST的真实应用6.1 Knuth优化把O(n^3)压到O(n^2)当n只有50的时候O(n^3)完全够用没有任何优化必要。但如果n到1000以上三重循环就不行了。这时候有一个教科书级的优化Knuth优化。核心结论是最优根r[i][j]满足单调性r[i][j-1] ≤ r[i][j] ≤ r[i1][j]也就是说在枚举k的时候不需要从i到j全部试一遍只需要从r[i][j-1]试到r[i1][j]即可。均摊下来总复杂度可以降到O(n^2)。但使用这个优化前必须验证w[i][j]满足四边形不等式。对于OBST的w区间概率和来说性质成立可以放心用。代码改动非常小for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; int L r[i][j - 1]; int R r[i 1][j]; double best INF; int bestK i; for (int k L; k R; k) { double val c[i][k - 1] c[k 1][j]; if (val best) { best val; bestK k; } } c[i][j] best w[i][j]; r[i][j] bestK; } }但注意优化后的边界条件比原版更敏感如果r矩阵初始化或者边界处理有疏漏很容易越界或者算错。我的建议是先把O(n^3)版本跑通确认答案无误后再考虑优化不要一上来就写Knuth优化版本。6.2 带失败概率的扩展和真实工程场景有些教材和PTA题面会给搜索失败的概率q[0]、q[1]、...、q[n]。这里的q[i]表示“落在关键字x[i]和x[i1]之间的值”被搜索的概率q[0]表示小于x1的值q[n]表示大于xn的值。此时w[i][j]的计算口径要扩展为w[i][j] sum_{ti}^{j} p[t] sum_{ti-1}^{j} q[t]c[i][i-1]也不再是0而是q[i-1]因为一个空区间对应一个失败结点搜索失败也要付出一次比较代价。递推结构不变只是w的来源变了。这就是我前面说的只要理解“深度下沉加w”的本质遇到带虚键的版本也能很快套上去。在真实工程里OBST常被用在“查找频率已知且长期稳定的静态键集合”场景比如字典的索引表、编译器里switch-case各分支频率的排序、数据库静态索引的构建。当数据量不大但查询频率差异明显时用OBST能比普通二叉搜索树或者简单顺序查找省下不少平均比较次数。最后说个我自己的习惯写完DP先别急着交用n3的小样例自己手算一遍再对着W、C、R矩阵逐项核对。矩阵对上了最优代价基本不会错。这道题真正难的不是代码量而是想明白递推式的每一个下标以及为什么根的选择要枚举而不是贪心。把这几点打通PTA上遇到任何变体的最优二叉搜索树你都能稳得住。
最优二叉搜索树从递推到实现：动态规划详解与C语言实战
最优二叉搜索树这道题在PTA上一出现基本就是算法设计与分析课程的“劝退题”。它没有现成的遍历模板可以套核心是要把动态规划的递推式真正搞明白再小心处理矩阵输出。我最初在PTA上刷7-3时代码跑不对的原因集中在三个地方状态初始化不对、区间枚举顺序反了、输出格式跟题面样例对不上。这篇文章不搞“贴个AC代码就跑”那一套而是把建模、递推推导、C语言实现、样例验证四个环节完整过一遍读完你可以做到既会写代码也能给别人讲清楚为什么这么写。下面按最常见的PTA版本讲给定n个互不相同的关键字x1 x2 ... xn以及每个关键字的搜索概率pi正实数要求构造一棵最优二叉搜索树使得查找成功时的期望比较次数最小并输出动态规划过程中的W、C、R三个矩阵。如果你拿到的题面还带搜索失败概率q[]也就是教材里说的“虚键”版本也不用慌递推式大体一致我后面会单独说明差异。1. 先看题目本质这不是让你“建一棵树”而是让你“选一棵树”1.1 题目输入输出背后的信息量题目输入通常只有两行第一行是n第二行是n个概率。信息量不大但仔细读能读出几个关键约束关键字序列严格递增这是二叉搜索树的天然性质也意味着中序遍历序列被固定了。不管树形怎么变每个结点的左右位置关系都要满足有序性。概率是正实数可能是整数也可能是0.1、0.15这种小数所以读入和处理都要按浮点数来。输出不只是最后的最优代价很多版本还要求输出三个矩阵W[i][j]区间概率和、C[i][j]最优期望代价、R[i][j]最优根下标。“中序遍历固定”这个话题值得多说一句。给定一组有序关键字能构造出多少棵不同的二叉搜索树答案是卡特兰数。比如n5时是42棵n10时是16796棵n20时已经是6564120420这种量级。所以题目本质上不是让你从零“建树”而是在所有可能的树形中“选一棵”代价最小的。每个区间[i, j]选择谁当根就唯一决定了一棵子树的结构最后拼出整棵树。1.2 读题时容易忽略的细节点我在PTA上见过不少同学包括当年的我因为下面的细节反复提交下标从1开始还是从0开始。建议统一从1开始这样空区间可以表示为[i, i-1]或者[j1, j]判断和初始化都方便。空子树的代价。当区间左端点大于右端点时表示没有结点代价是0。这在递推中会反复用到。输出保留几位小数。很多版本要求两位小数用%.2f也有要求四位或六位的必须看题面。多个最优解取哪个根。有些题目会明确说“如果存在多个最优解输出编号较小的根”没说的话按第一个找到的最优k处理即可。这几个点看起来小但每一个都直接决定你是否能AC。尤其是最后一个如果题目对R矩阵有要求平局处理不一致会导致矩阵输出跟样例对不上一查一个准。2. 为什么“每次让最大概率当根”救不了你2.1 一个三节点反例很多人第一反应是谁被搜得多谁就该当根这不就是贪心吗我们用一个三结点例子把它否决掉。假设三个关键字x1、x2、x3概率分别是p10.3、p20.3、p30.4。概率最大的是x3按照贪心思路把x3放根上。剩下x1、x2在左子树。左子树有两种挂法左子树根x1x2是x1的右孩子。整棵树深度x3在深度1x1在深度2x2在深度3。期望代价 0.4×1 0.3×2 0.3×3 1.9。左子树根x2x1是x2的左孩子。整棵树深度x3在深度1x2在深度2x1在深度3。期望代价 0.4×1 0.3×2 0.3×3 1.9。所以不管左子树怎么排贪心版本的代价都是1.9。但如果让x2当根x1挂左、x3挂右深度分别是x2深度1x1深度2x3深度2。期望代价 0.3×1 0.3×2 0.4×2 1.7。1.7 1.9贪心输了。这个例子很能说明问题概率最大的x3当根只省下了自己那一层却把两个0.3概率的结点压到了深度2和深度3让x2当根x3虽然从深度1变成深度2只是多付出0.4但x1保持深度2x2本身也只深度1。根的选择会影响整棵子树所有结点的深度这是一种全局连锁局部最优根本顶不住。2.2 最优子结构与重叠子问题既然贪心不行那就要枚举。枚举的核心观察是一旦选定根k左子树[i, k-1]和右子树[k1, j]各自的最优结构是独立的互不影响。这就满足动态规划的最优子结构。另一个特征是重叠子问题。比如要算c[1][5]枚举根时会反复用到c[2][4]、c[3][4]等子区间而要算c[2][4]又要用到更小的区间。同一个子问题被不同的上层问题重复求解如果直接递归代价是卡特兰数级别的。用一张二维表把每个区间的最优值存下来每个区间只算一次总复杂度就从指数级降到O(n^3)。顺带说一句很多人会拿OBST和哈夫曼树做对比。两者确实都在给带权结点排队但哈夫曼树把所有数据都放在叶子且不要求中序遍历有序OBST的所有关键字都在内部结点且必须保持二叉搜索树的有序性。理解这个区别后面看优化方向会清楚很多。3. 递推式的建立一次“深度下沉”的思想实验3.1 先定义清楚c[i][j]表示什么在写代码之前务必将状态定义刻在脑子里w[i][j]区间[i, j]内所有概率之和即sum_{ti}^{j} p[t]。c[i][j]由关键字x[i..j]构成的最优二叉搜索树在“子树根深度为1”的度量下查找成功时的最小期望比较次数。r[i][j]达到最优值时的根下标k。“子树根深度为1”这个定义很重要。查找一个深度为d的结点需要比较d次命中根节点只需要比较1次所以根的贡献就是p[k]×1。3.2 从“把子树挂到根下面”推导转移方程假设区间[i, j]选择k作为根。先单独看左子树[i, k-1]。这棵子树内部的最优期望代价是c[i][k-1]但这个值是在“左子树根深度为1”的前提下算出来的。现在左子树被挂到k的左边实际深度整体下沉一层左子树里每个结点的比较次数都要加1。左子树所有结点的概率之和是w[i][k-1]所以左子树真实贡献变成c[i][k-1] w[i][k-1]同理右子树真实贡献是c[k1][j] w[k1][j]根k本身的贡献是p[k]。三者相加total p[k] c[i][k-1] w[i][k-1] c[k1][j] w[k1][j]把w和p并在一起看p[k] w[i][k-1] w[k1][j] w[i][j]因为w[i][j]定义就是整个区间所有概率之和。于是得到最简形式c[i][j] w[i][j] min_{i≤k≤j}(c[i][k-1] c[k1][j])这个式子就是整道题的核心。很多同学背下来了但不知道“深度下沉”那一层含义遇到带虚键的变形就懵了。其实只要记住“子树挂到根下面深度加1代价增加w”什么变形都能推。3.3 边界条件空子树代价为零当i j时区间没有关键字期望代价为0。代码里C数组是全局变量默认就是0所以不需要特别初始化。单点区间[i, i]也不需要特殊处理用递推式算一遍c[i][i] w[i][i] min(c[i][i-1] c[i1][i]) p[i] 0 p[i]正好等于单结点树的期望代价。这说明递推式对长度为1的区间也自洽。w[i][j]则建议用前缀和计算定义sumP[t] sum_{s1}^{t} p[s]则w[i][j] sumP[j] - sumP[i-1]。这样在任何地方取w都是O(1)不会额外增加复杂度。4. 用C语言实现从递推式到可运行代码4.1 数据结构、输入与初始化n的范围一般是50以内数组开到55就足够。注意C数组在访问c[i][k-1]时k-1可能等于i-1最小为0在访问c[k1][j]时k1可能等于j1最大为n1所以数组第二维至少开到n2。#include stdio.h #define MAXN 55 #define INF 1e18 double p[MAXN]; double sumP[MAXN]; double w[MAXN][MAXN]; double c[MAXN][MAXN]; int r[MAXN][MAXN]; int n;读入部分scanf(%d, n); for (int i 1; i n; i) { scanf(%lf, p[i]); sumP[i] sumP[i - 1] p[i]; }随后预处理w矩阵。w[i][j]只在j i时有效其他位置保持0即可for (int i 1; i n; i) { for (int j i; j n; j) { w[i][j] sumP[j] - sumP[i - 1]; } }单点区间可以直接初始化也可以交给后面的递推二选一。为了减少出错的环节我更推荐把它交给递推统一处理这样少一段代码少一个地方出错。但很多教材版代码里会先写一句c[i][i] p[i]也完全没问题只要保证后面不重复覆盖。4.2 区间DP的循环顺序为什么要按长度递增主循环务必按区间长度从小到大算。当你在算长度len的区间时会访问长度小于len的c[i][k-1]和c[k1][j]这些值必须在之前已经算好。最不容易绕晕的写法是for (int len 1; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; double best INF; int bestK i; for (int k i; k j; k) { double val c[i][k - 1] c[k 1][j]; if (val best) { best val; bestK k; } } c[i][j] best w[i][j]; r[i][j] bestK; } }这里len从1开始是因为递推式对单点区间自洽len1时会算出c[i][i] p[i]。这种写法在初始化上最省心也不用担心漏掉哪个单点。有人喜欢写for (int i n; i 1; i--)再从j i开始本质上也是保证子区间更短但容易下标绕晕。我建议新手一律用长度递增直观且不容易错。4.3 矩阵输出与递归还原最优树如果题目要求输出W、C、R三个矩阵通常以“上三角”形式输出。下面是一种典型写法每个数值占7.2f的宽度空位用空格填充for (int i 1; i n; i) { for (int j 1; j n; j) { if (j i) { printf( ); } else { printf(%7.2f, w[i][j]); } } printf(\n); }C矩阵同理把w换成c。R矩阵是整数格式改为%6dfor (int i 1; i n; i) { for (int j 1; j n; j) { if (j i) { printf( ); } else { printf(%6d, r[i][j]); } } printf(\n); }如果题目要求输出最优树结构利用R矩阵可以递归还原。R[1][n]是整棵树的根然后递归处理左右子树先序遍历就是void printTree(int i, int j) { if (i j) { return; } int k r[i][j]; printf(%d , k); printTree(i, k - 1); printTree(k 1, j); }把这三段组合起来补上main函数框架就是一份完整的AC代码。完整可运行的代码我在文末给一个整理版方便直接对照。5. 样例验证与踩坑复盘5.1 手推一个三节点样例用2.1那个反例做验证p {0.3, 0.3, 0.4}。先算所有ww[1][1] 0.3w[2][2] 0.3w[3][3] 0.4w[1][2] 0.6w[2][3] 0.7w[1][3] 1.0len 1时c[1][1] 0.3r[1][1] 1c[2][2] 0.3r[2][2] 2c[3][3] 0.4r[3][3] 3len 2时区间[1,2]k1时val c[1][0] c[2][2] 0.3k2时val c[1][1] c[3][2] 0.3。两者都是0.3加w[1][2]0.6得到c[1][2]0.9。按“第一个最优k”原则r[1][2]1。区间[2,3]k2时val c[2][1] c[3][3] 0.4k3时val c[2][2] c[4][3] 0.3。取较小的0.3加w[2][3]0.7得到c[2][3]1.0r[2][3]3。len 3时区间[1,3]k1c[1][0] c[2][3] 0 1.0 1.0k2c[1][1] c[3][3] 0.3 0.4 0.7k3c[1][2] c[4][3] 0.9 0 0.9最小值是0.7取k2。加w[1][3]1.0得到c[1][3]1.7r[1][3]2。跟前面手算的1.7完全对上了。用R矩阵还原树整树根是2左区间[1,1]的根是1右区间[3,3]的根是3先序序列是2 1 3结构就是x2在根、x1在左、x3在右。5.2 输出格式的隐坑空格、占位符与矩阵对齐输出格式是这道题最容易无缘无故扣分的地方。很多PTA题目的矩阵输出对占位符宽度有严格要求%7.2f和%6d是我个人比较常用的组合但它不一定匹配你的题面。务必以题目给的“输出样例”为准样例里一位整数占几个空格你就用几个宽度样例空位用什么填充你就用什么填充。最稳妥的方法是把样例输出下载下来自己程序跑一遍后逐字符比对尤其是行末有没有多余空格、空位是0还是空白。如果题目要求输出完整n×n矩阵而不是上三角把else分支去掉改成统一输出即可。注意此时j i的区域到底补0.00还是留空题面通常会写明。5.3 我在调试中遇到的三个典型bug这三个bug都是实际调过、翻过车的列出来给大家避坑。第一单点区间初始化遗漏。如果采用“先初始化c[i][i] p[i]”的写法有一项漏掉会导致后面所有依赖它的区间计算结果偏小而且偏小的数值特别隐蔽你不容易看出是哪里错了。反过来如果用len从1开始的统一递推写法就不会有这个风险。第二INF设置过小。概率虽然是小数但如果题目给出的概率数值很大或者你选择的权值单位不同1e9这种规模可能会被真实答案逼近。稳妥做法是直接给1e18反正double溢出不了。第三平局根的选择不一致。如果题面要求“多个最优解输出编号最小的根”那么更新条件应该用if (val best - 1e-9)只有严格小于才更新如果要求编号最大的根用if (val best 1e-9)更新。这里引入1e-9容差是为了避免浮点误差导致平局判定错误。还有一个小细节题目如果没说平局规则一般以第一个k为准即if (val best)。6. 进阶四边形不等式优化与OBST的真实应用6.1 Knuth优化把O(n^3)压到O(n^2)当n只有50的时候O(n^3)完全够用没有任何优化必要。但如果n到1000以上三重循环就不行了。这时候有一个教科书级的优化Knuth优化。核心结论是最优根r[i][j]满足单调性r[i][j-1] ≤ r[i][j] ≤ r[i1][j]也就是说在枚举k的时候不需要从i到j全部试一遍只需要从r[i][j-1]试到r[i1][j]即可。均摊下来总复杂度可以降到O(n^2)。但使用这个优化前必须验证w[i][j]满足四边形不等式。对于OBST的w区间概率和来说性质成立可以放心用。代码改动非常小for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; int L r[i][j - 1]; int R r[i 1][j]; double best INF; int bestK i; for (int k L; k R; k) { double val c[i][k - 1] c[k 1][j]; if (val best) { best val; bestK k; } } c[i][j] best w[i][j]; r[i][j] bestK; } }但注意优化后的边界条件比原版更敏感如果r矩阵初始化或者边界处理有疏漏很容易越界或者算错。我的建议是先把O(n^3)版本跑通确认答案无误后再考虑优化不要一上来就写Knuth优化版本。6.2 带失败概率的扩展和真实工程场景有些教材和PTA题面会给搜索失败的概率q[0]、q[1]、...、q[n]。这里的q[i]表示“落在关键字x[i]和x[i1]之间的值”被搜索的概率q[0]表示小于x1的值q[n]表示大于xn的值。此时w[i][j]的计算口径要扩展为w[i][j] sum_{ti}^{j} p[t] sum_{ti-1}^{j} q[t]c[i][i-1]也不再是0而是q[i-1]因为一个空区间对应一个失败结点搜索失败也要付出一次比较代价。递推结构不变只是w的来源变了。这就是我前面说的只要理解“深度下沉加w”的本质遇到带虚键的版本也能很快套上去。在真实工程里OBST常被用在“查找频率已知且长期稳定的静态键集合”场景比如字典的索引表、编译器里switch-case各分支频率的排序、数据库静态索引的构建。当数据量不大但查询频率差异明显时用OBST能比普通二叉搜索树或者简单顺序查找省下不少平均比较次数。最后说个我自己的习惯写完DP先别急着交用n3的小样例自己手算一遍再对着W、C、R矩阵逐项核对。矩阵对上了最优代价基本不会错。这道题真正难的不是代码量而是想明白递推式的每一个下标以及为什么根的选择要枚举而不是贪心。把这几点打通PTA上遇到任何变体的最优二叉搜索树你都能稳得住。