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

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

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

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

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

#Алгоритм

Воспользуемся полученными неравенствами самым прямым образом: будем для каждого состояния просто перебирать все элементы от $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 строчки длиннее, чем базовое решение.

#Асимптотика

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