Пересчет динамики по слоям

Задача. Даны $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 связанных между собой способа её соптимизировать, помимо непосредственно этой задачи обобщающихся и на многие другие динамики.