Pattern - Quadrangle Optimizations

When cost satisfies QI, optimal splits are monotonic. This lets you prune the search space.

$1.$ Identify the DP type: Layered (partitioning) → D&C. Interval (combining) → Knuth.

$2.$ Prove QI: $cost(a,c) + cost(b,d) \leq cost(a,d) + cost(b,c)$.

$3.$ Apply the improvement: Use divide-and-conquer or double bounds.

$4.$ Track opt values: They bound future computations. This improvement reduces redundant work largely.