Knuth's optimization in Dynamic Programming

Knuth's optimization is used to optimize the run-time of a subset of Dynamic programming problems from O(N^3) to O(N^2).

Properties of functions

Some properties of two-variable functions required for Kunth's optimzation:

1. Quadrangle inequalities

For a two-variable function $f(x, y)$ :

Convex quandrangle inequality : $\forall_{a \leq b \leq c \leq d}(f(a, c) + f(b, d) \leq f(a, d) + f(b, c))$

Concave quadrangle inequality : $\forall_{a \leq b \leq c \leq d}(f(a, c) + f(b, d) \geq f(a, d) +...