Последняя лекция про динамическое программирование

1. Ещё про хроматическое число
1.1 Ещё раз про 3^n + 2^n
1.2 Общая концепция: перебирать только максимальное по включению
1.3 Алгоритм перебора максимальных по включению
1.4 max_k k^{1/k} = 1.4423
1.5 Добавляем в старую задачу, получаем 2.4423^n

2. Meet In The Middle
2.1 Subset sum, умеем за nS, 2^n.
2.2 Делим пополам, получаем 2^{n/2} (с хештаблицей) или 2^{n/2} n (с бинпоиском)
2.3 Рюкзак со стоимостями, получаем 2^{n/2} n
2.4 Клики, получаем 2^{n/2} poly(n)
2.5 Клики через рекурсивный перебор

3. Дп по изломанному профилю
3.1 Как перебор с запоминанием
3.2 Два слова про на массиве

4. [skip] битовые радости: реверс, set cover