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

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

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

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

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