Постановка задачи

Пусть $$$w(j, i)$$$ — некоторая функция стоимости, которую мы умеем вычислять за $$$O(1)$$$ и для которой выполняется неравенство четырехугольника:

$$$w(a, c) + w(b, d) \le w(a, d) + w(b, c)$$$, где $$$a \le b \le c \le d$$$.

Наша задача: посчитать динамику вида $$$dp[i] = \min\limits_{0 \le j < i} dp[j] + w(j, i)$$$ (будем считать, что $$$dp[0] = 0$$$) быстрее, чем за $$$O(n^2)$$$, где $$$n$$$ — размер нашей динамики.