Задача. Даны $n$ точек на прямой, отсортированные по своей координате $x_i$. Нужно найти $m$ отрезков, покрывающих все точки, минимизировав при этом сумму квадратов их длин.
Базовое решение — определить состояние динамики $f[i, j]$ как минимальную стоимость покрытия $i$ первых точек используя не более $j$ отрезков. Пересчитывать её можно перебором всех возможных последних отрезков:
$$ f[i, j] = \min_{k < i} \{f[k, j-1] + (x_{i-1}-x_k)^2 \} $$Итоговым ответом будет $f[n, m]$, а суммарно такая динамика будет работать за $O(n^2 m)$.
// x[] — отсортированный массив координат точек, индексация с нуля
// квадрат длины отрезка с i-той до j-той точки
int cost(int i, int j) {
return (x[j] - x[i]) * (x[j] - x[i]);
}
for (int i = 0; i <= m; i++)
f[0][i] = 0; // если нам не нужно ничего покрывать, то всё и так хорошо
// все остальные f предполагаем равными бесконечности
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 0; k < i; k++)
f[i][j] = min(f[i][j], f[k][j - 1] + cost(k, i - 1));
(Заметим, что циклы по i и j можно поменять местами.)
В этой главе мы рассмотрим 4 связанных между собой способа её соптимизировать, помимо непосредственно этой задачи обобщающихся и на многие другие динамики.