Эта статья — одна из серии. Рекомендуется сначала прочитать все предыдущие.
Предыдущий метод оптимизации опирался на тот факт, что $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)$.