Knuth 区间动态规划优化

右端增加一个元素时，最佳根不会被迫向左越过原来的最左最优根；左端删掉一个元素时，最佳根也不会向左移动。这两条方向约束合在一起，把当前根夹在两个较短区间的根之间。

为什么需要增量条件？证明分两层。第一层是 Yao 的继承引理：上述 $W$ 的四点不等式和包含单调性，使最优值 $D$ 也满足同向的区间四点不等式。按外层区间长度归纳，取右侧两个最优区间的根；按两根的先后次序，把它们交叉用于左侧两区间。子区间的四点差由归纳假设控制，新增的 $W$ 项由四点条件控制；两区间只在端点相接的基例则要用包含单调性。这也是不能遗漏第二个条件的原因。

第二层从 $D$ 的四点性质推出根边界。看左边界，若 $q=R[i,j]$ 比 $p=R[i,j-1]$ 小，那么在旧区间里，较小的 $q$ 必须严格劣于 $p$，否则违反最左规则。四点不等式给出

加上相同的左子树差 $D[i,q]-D[i,p]$，说明延长右端后 $q$ 相对 $p$ 更不可能变好，矛盾。右边界的证明对称地比较左子树；若出现平局，较小根仍由最左规则获胜。因此这份实现虽然与原论文常用的最右平局约定不同，仍保持相同方向的边界。

成功查找频率为 3、1、4、2 ​

给四个有序键 $q_0<q_1<q_2<q_3$，成功查找频率为 $f=(3,1,4,2)$。要构造一棵二叉搜索树公理库二叉搜索树Binary search tree · BST每个结点左子树键小于、右子树键大于该结点键的二叉树。，最小化“频率乘访问比较次数”的总和，根上的键算一次比较。

选根 $k$ 后，左右子树中每次查找都会多比较一次，所以增量是

非负频率保证包含单调性；四点不等式在这里恰为等式。长度一的代价为 $(3,1,4,2)$；长度二的代价与最左根为

算 $[1,4)$ 时，左右边界 $R[1,3]=R[2,4]=2$，只检查根 $2$，得到 $D[1,4]=1+2+7=10$。算 $[0,3)$ 得到最优根 $2$、代价 $13$。于是整个 $[0,4)$ 又被两个根 $2$ 夹住，只检查

重建的树以 $q_2$ 为根，左孩子 $q_0$ 的右孩子为 $q_1$，右孩子为 $q_3$。实际加权比较次数为 $4\cdot 1+3\cdot 2+1\cdot 3+2\cdot 2=17$，与表值吻合。完整枚举所有区间共检查 $20$ 个根，本例的边界优化检查 $15$ 个；小例子的节省有限，但增长阶不同。

区间递推的外形不够 ​

矩阵链乘法也在区间中枚举切点，却含有依赖切点的乘法代价，不能直接归入这里的 $W(i,j)$。取矩阵维数 $2\times 3,3\times 2,2\times 10,10\times 1$：前三个矩阵的最佳顶层切点在第二个矩阵后，四个矩阵的最佳顶层切点却在第一个矩阵后。根向左倒退，正好破坏需要的单调性。

零频率不会破坏条件，但会产生大量平局；统一最左规则后边界仍成立。负频率则不再是查找概率或访问次数，并且可能破坏包含单调性。对新问题应逐项验证增量与边界，而不是根据几个小表的根刚好有序就套用优化。

固定长度 $L\ge 2$，区间 $[i,i+L)$ 扫描的根数为

沿 $i$ 求和，前一项与下一段的后一项来自同一条长度 $L-1$ 的根对角线，内部差望远镜相消，只留下两个端点和 $O(n)$ 个常数。因此每个长度总共 $O(n)$ 次枚举，全部长度总共 $O(n^2)$。这不是声称每个区间只看常数个根；某个区间仍可很宽，只是同一长度的总宽度受控。

前缀和让 $W$ 常数时间可得，表值与根表占 $O(n^2)$ 空间。根表还能递归输出整棵最优树。若只保留部分对角线却仍要任意访问左右子树费用，需另做存储分析，不能像普通分层 DP 那样直接压成两行。

分治 DP 优化公理库决策单调的分治 DP 优化Divide-and-conquer DP optimization在已证明最优切点单调的分层递推中，先求中间状态，再用它收紧左右候选区间，逐层安全省去转移。依靠一层内的单向切点次序；本页依靠两个重叠区间给出的双边界，并以区间长度调度计算。辨认递推依赖的形状，才能知道该使用哪一种单调性。