Изменения

Теперь формула приняла вид <math>dp[i] = min_{j=0...i-1}(k[j]*x[i] + b[j])</math>. Выражение <math>k[j]*x + b[j]</math> напоминает уравнение прямой <math>y = kx + b</math>. Сопоставим каждому <math>j</math>, обработанному ранее прямую <math>y[j](x) = k[j]*x + b[j]</math>. Из условия «<math>c[i]</math> убывают <math><=> k[j]</math> уменьшаются с номером <math>j</math>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффицента. Давайте нарисуем несколько таких прямых :

Итак, давайте выделим множество точек <math>(x0, y0)</math> , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <math>y’(x)</math>, такой что <math>y’(x0) < y0</math>. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых. На катинке множество точек выделено жирным оранжевым цветом и представляет собой выпуклую вверх функцию. Назовем ее «<math>y = convex(x)</math>»