Изменения

==О-ОптимизацияКлючевая идея оптимизации==1) Сделаем замену обозначений. Давайте обозначим <math>dp[j]</math> за <math>b[j]</math>, <math>a[i]</math> за <math>x[i]</math>, а <math>c[j]</math> за <math>k[j]</math>.2) Теперь формула приняла вид <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>. 3) Сопоставим каждому <math>j</math>, обработанному ранее , прямую <math>y[j](x) = k[j]*x + b[j]</math>. Из условия «<math>c[i]</math> убывают <math><=> k[j]</math> уменьшаются с номером <math>j</math>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент. Давайте нарисуем несколько таких прямых :

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