“给定 $m\ge0$ 个有序行号、$n\ge1$ 个有序列号,以及能在 $O(1)$ 时间返回 $A {r,c}$ 的接口,若矩阵对最左行极小值全单调,SMAWK 可用 $O(m+n)$ 次…”
形式陈述
一张表的各行最小列恰好从左往右排列,是否就可以删去一些列、递归搜索剩下的表?不一定。删除可能露出原来被更小元素遮住的逆序。全单调矩阵要求这种顺序在所有子矩阵中都保留。
设
这个定义等价于以下二行二列条件:对于
也就是说,上行右列严格优于左列时,下行也必须如此。此处前提、结论都用严格大于,配合“最左”平局约定。如果改成选最右极小值,应使用相应的另一套比较规则,不能只把代码中的符号零散替换。
直觉
全单调性保存的不是数值大小,而是候选之间的胜负方向。在两列之间,越往下走,右边候选可以从落后变成领先;一旦严格领先,就不能重新落后或打平到让最左规则偏向左边。
为什么只看
定义中的“所有子矩阵”听来庞大,二列胜负规则却把它变成局部逻辑。也正因为删列以后仍然成立,递归搜索才有稳定的前提。
例子与边界
原表单调,子表不单调
取
两行最左极小列都是
上行选右列,下行选左列,次序逆转。严格比较也直接揭示失败:
全单调也不要求四点和满足 Monge
考虑
两行都偏好左列。上行“右列严格更好”的前提不成立,故唯一的
Monge 推出全单调,是因为四点不等式保证
一个等号为什么会改变正确性
再看
按最左规则,两行都选第一列,
在全零矩阵里,每行可以随意选一个最小位置,但这样记录出的答案可能倒退;这不反驳矩阵的全单调性,只说明选点规则没有遵守定义。实现中保存并比较二元组“数值、原列号”,是让最左规则贯穿所有递归层的直接办法。
推论与应用
全单调性对保序删行、删列封闭,因而适合“删除不可能赢的列,再递归求部分行”的搜索。SMAWK 算法正是利用这一点,把一个
有些 DP 表只定义在阶梯形可行域上,例如候选切点必须满足
实际使用有三层不同的检查:先由模型证明全单调性,再用小规模穷举验证平局和边界实现,最后才使用快速搜索。随机测试没有发现逆序,不能代替第一层证明;但它很擅长发现把严格比较写成非严格比较、把原列号换成局部列号等实现失误。