Divide and Conquer Optimization in Dynamic Programming

Divide and conquer optimization is used to optimize the run-time of a subset of Dynamic Programming problems from $O(N^2)$ to $O(N logN)$.

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) + f(b, c))$

Optimization criteria

A dynamic programming problem of the form:

$$

dp(i...