Knuth Optimization

释义（Definition）

Knuth Optimization（克努斯优化）是一种用于特定区间动态规划（interval DP）的优化技巧：当代价函数满足一定条件（常见表述为四边形不等式 / Quadrangle Inequality与决策单调性）时，可以把转移中最优决策点的搜索范围缩小，从而常把朴素的 O(n³) 优化到 **O(n²)**。

（该术语主要出现在算法竞赛与算法课程语境中。）

发音（Pronunciation, IPA）

/kəˈnuːθ ˌɒptɪmaɪˈzeɪʃən/

例句（Examples）

Knuth optimization can speed up some interval DP problems.
Knuth 优化可以加速某些区间动态规划问题。

When the cost function satisfies the quadrangle inequality, Knuth optimization often reduces the DP complexity from O(n^3) to O(n^2) by exploiting monotonicity of the optimal split points.
当代价函数满足四边形不等式时，Knuth 优化常利用最优断点的单调性，把 DP 复杂度从 O(n³) 降到 O(n²)。

词源（Etymology）

“Knuth”来自美国计算机科学家 Donald E. Knuth（唐纳德·克努斯）的姓氏；“optimization”意为“优化”。该名词用来指代与他相关、并在区间 DP 中广为人知的一类优化思想与结论，因此被称为 “Knuth Optimization”。

相关词（Related Words）

• Dynamic Programming
• Interval DP
• Divide And Conquer Optimization
• Quadrangle Inequality
• Monge Array
• SMAWK
• Convex Hull Trick

文学与著作中的用例（Literary / Notable Works）

• Competitive Programming 3（Steven Halim 等）：在 DP 优化章节/讨论中常提及 Knuth optimization。
• Competitive Programmer’s Handbook（Antti Laaksonen）：以竞赛视角介绍包括 Knuth optimization 在内的 DP 优化技巧。
• CP-Algorithms（在线算法手册，cp-algorithms.com）：有专门条目讨论 Knuth optimization 的适用条件与实现要点。