Монотонность точки перегиба

Пусть в рамках какой-то задачи мы считали "слоистую" динамику $dp_{i, j}$, пересчет которой выглядел (в общем случае):

$$dp_{i, j} = \min_{k=1}^{j-1} \{dp_{i-1,k} + f(k + 1, j)\}$$

Обозначим $opt_{i, j} = \argmin_{k=1}^{j-1} \{dp_{i-1,k} + f(k + 1, j)\}$ (а среди всех минимумов --- с меньшим $j$). Тогда в большом количестве задач функция $opt_{i, j}$ монотонна.

Например, пусть мы решали задачу о разбиении $n$ положительных чисел на $k$ отрезков с минимальной суммой квадратов их сумм. Тогда $opt_{i, j - 1} \le opt_{i, j}$, потому что $$\forall k < j : dp_{i, k} + (\sum_{t=k}^{j - 1} x_t)^2 \ge dp_{i, opt_{i, j - 1}} + (\sum_{t=opt_{i, j - 1}}^{j - 1} x_t)^2 $$

Теперь докажем от противного, что $opt_{i, j} \ge opt_{i, j - 1}$. Пусть существовал элемент $v < opt_{i, j}$, для которого выполнялось

$$dp_{i, v} + (\sum_{t=v}^{j} x_t)^2 < dp_{i, opt_{i, j - 1}} + (\sum_{t=opt_{i, j - 1}}^{j} x_t)^2 $$

$$dp_{i, v} + (\sum_{t=v}^{j} x_t)^2 - (\sum_{t=opt_{i, j - 1}}^{j} x_t)^2 < dp_{i, opt_{i, j - 1}}$$

Обозначим $s = \sum_{t=v}^{opt_{i, j - 1} - 1} x_t$

$$dp_{i, v} + s \cdot (s + 2 \cdot \sum_{t=opt_{i, j - 1}}^{j} x_t) < dp_{i, opt_{i, j - 1}}$$

Но тогда $$dp_{i, v} + s \cdot (s + 2 \cdot \sum_{t=opt_{i, j - 1}}^{j - 1} x_t) \le dp_{i, opt_{i, j - 1}}$$, чего не может быть, потому что $v != opt_{i, j - 1}$.

Разумеется, в реальных задачах никто ничего не доказывает, потому что утверждение о монотонности обычно интуитивно понятно.

Зачем это нужно?

При разного рода монотонностях точки перегиба можно применять разные оптимизации динамики:

• $opt_{i, j} \le opt_{i, j + 1}$ --- Divide&Conquer оптимизация
• $opt_{i - 1, j} \le opt_{i, j} \le opt_{i, j + 1}$ --- оптимизация Кнута