Оптимизация Кнута - Алгоритмика
Оптимизация Кнута

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

Эта статья — одна из серии. Рекомендуется сначала прочитать все предыдущие.

Предыдущий метод оптимизации опирался на тот факт, что $opt[i, j] \leq opt[i, j + 1]$.

Асимптотику можно ещё улучшить, заметив, что $opt$ монотонен ещё и по первому параметру:

$$ opt[i-1, j] \leq opt[i, j] \leq opt[i, j+1] $$

В задаче про покрытие отрезками это выполняется примерно по той же причине: если нам нужно покрывать меньше точек, то новый оптимальный последний отрезок будет начинаться не позже старого.

Алгоритм

Воспользуемся полученными неравенствами самым прямым образом: будем для каждого состояния просто перебирать все элементы от $opt[i - 1, j]$ до $opt[i, j + 1]$.

Чтобы к тому моменту, когда мы дойдем до состояния $(i, j)$, границы $opt[i - 1, j]$ и $opt[i, j + 1]$ были уже посчитаны, мы будем проходиться в порядке увеличения $i$ и уменьшения $j$.

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 = f[i + 1][k-1] + cost(i, j);
            if (val < f[t][k])
                f[t][k] = val, opt[i][j] = i;
        }
    }
}

Реализация получилась очень лаконичной: она всего на 3 строчки длиннее, чем базовое решение.

Асимптотика

Выясняется, что это работает быстро. Чтобы понять, почему, распишем количество элементов, которые мы просмотрим для каждого состояния, и просуммируем:

$$ \sum_{i, j} (opt[i, j+1] - opt[i-1, j] + 1) = nm + \sum_{ij} (opt[i, j+1] - opt[i-1, j]) $$ Заметим, что все элементы, кроме граничных, учитываются в сумме ровно два раза — один раз с плюсом, другой с минусом — а значит их можно сократить. Граничных же элементов $O(n)$, и каждый из них порядка $O(n)$. Значит, итоговая асимптотика составит $O(n \cdot m + n \cdot n) = O(n^2)$.