Динамика. Обычная и по подмножествам.

Динамика: вперед, назад, рекурсивно-ленивая (на примере задачи про калькулятор)
Динамика и ацикличный граф
Рюкзак: только веса, ценностей нет. Решение за \(O(nW)\) и \(O(W)\) памяти с восстановлением ответа. Использование bitset.
Наибольшая общая подпоследовательность двух, трех, сжатие памяти.
Динамика на подотрезках и строки: LCP, folding, LZSS
Битовые операции (объединение, пересечение, разность множеств и т.д.)
Динамика по подмножествам
- Сумма на подмножестве, количество бит в числе, старший бит, младший бит.
- Проверка для каждого множества, независимое ли оно.
- Гамильтонов путь за \(O(2^nn^2)\) времени, за \(O(2^nn)\) времени.
- Гамильтонов путь за \(O(2^nn)\) времени.
Перебор всех подмножеств. Раскраска графа в минимальное количество цветов за \(O(3^n)\)
Динамика по скошенному профилю = перебор + полиномиальный хеш + запоминание хеш-таблицей