# 最优二叉检索树: 补充解法

## 完整枚举根：出题人解法

[alternative.cpp](alternative.cpp) 对每个非空区间枚举全部根 $k\in[l,r]$ ，以 $D(l,k-1)+D(k+1,r)+W(l,r)$ 更新最优值。空区间为零，单点区间代价为对应访问次数。区间按长度递增计算；前缀和在常数时间提供 $W$ .

根从小到大枚举，仅在代价严格变小时更新。因此同代价时保留最小根。按根、左、右输出时，该规则在每层独立保证最小先序；证明及迭代重建见[主解](solution.zh.md)。每个合法树的根与两棵子树均被包含，所以取最小值正确。

时间 $O(n^3)$ ，空间 $O(n^2)$ .该方案不需要根单调性，便于检查递推与平局规则，并支持本题全部数据；首选 Knuth 程序将时间降到平方级。Codex（GPT-6）保留出题人的枚举和选根策略，使用按输入大小分配的数组与显式输出栈。