Problem statement

Let $$$w(j, i)$$$ be some cost function that we are able to calculate in $$$O(1)$$$ and which satisfies quadrangle inequality:

$$$w(a, c) + w(b, d) \le w(a, d) + w(b, c)$$$ for $$$a \le b \le c \le d$$$.

The problem is to calculate the following dynamic programming: $$$dp[i] = \min\limits_{0 \le j < i} dp[j] + w(j, i)$$$ (let's initialize $$$dp[0] = 0$$$) faster than in $$$O(n^2)$$$, where $$$n$$$ is the size of the dynamic programming.