Динамическое программирование по интервалам

(Для удобства записи мы также разрешим ссылки OPT(i, j) даже при i > j; в этом случае значение равно 0).

Теперь в оптимальной вторичной структуре bibi+1 ... bj существуют те же альтернативы, что и прежде:

• j не участвует в паре; или
• j находится в паре с t для некоторого t < j −

В первом случае имеем OPT(i, j) = OPT(i, j − 1). Во втором случае, изображенном на рис. 6.15, b, порождаются две подзадачи OPT(i, t − 1) и OPT(t + 1, j − 1); как было показано выше, эти две задачи изолируются друг от друга условием отсутствия пересечений.

Следовательно, мы только что обосновали следующее рекуррентное отношение:

(6.13) OPT(i, j) = max(OPT(i, j – 1), max(1 + OPT(i, t – 1) + OPT(t + 1, j – 1))), где

max определяется по t, для которых bt и bj образуют допустимую пару оснований (с учетом условий (i) и (ii) из определения вторичной структуры).

Теперь нужно убедиться в правильном понимании порядка построения решений подзадач. Из (6.13) видно, что решения подзадач всегда вызываются для более коротких интервалов: тех, для которых k = j − i меньше. Следовательно, схема будет работать без каких-либо проблем, если решения строятся в порядке возрастания длин интервалов.