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

Пусть мы хотели посчитать $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)$.

1 for (int i = 1; i <= n; i++) {
2     for (int j = m; j >= 1; j--) {
3         for (int k = opt[i-1][j]; k <= opt[i][j+1]; k++) {
4             int val = cost(i, j, k);
5             if (val < f[i][j])
6                 f[i][j] = val, opt[i][j] = k;
7         }
8     }
9 }

---

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

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