Оптимизация Кнута

Пусть мы хотели посчитать $dp_{i, j} = \max_{k=1}^i f(i, j, k}$, которая удовлетворяла [монотонность точки перегиба|монотонности точки перегиба]] сразу по двум параметрам (иначе говоря, для нее $opt_{i - 1, j} \le opt_{i, j} \le opt_{i, j + 1}$. Тогда можно перебирать параметры пересчета динамики в таком порядке, чтобы для пары $\{i, j\}$ уже были известны $opt_{i - 1, j}, opt_{i, j + 1}$. Если пересчитывать динамику, используя это приближение, то суммарное количество операций будет $O(n^2)$. Действительно, для всех $i, j : j - i = const$ мы суммарно рассмотрим $O(n)$ точек перегиба, а разных значений этой функции бывает $O(n)$.

<syntaxhighlight lang='c++' line='line> for (int i = 1; i <= n; i++) {

   for (int j = m; j >= 1; j--) {
       for (int k = opt[i-1][j]; k <= opt[i][j+1]; k++) {
           int val = cost(i, j, k);
           if (val < f[i][j])
               f[i][j] = val, opt[i][j] = k;
       }
   }

} </syntaxhihlight>

---

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s