Динамика (27 февраля 2014)

1. Задачи
1. Наибольшая общая двух за O(n²)
2. Наибольшая общая трех за O(n³)
3. Наибольшая общая возрастающая за O(n³), O(n²)
2. Пример: наибольшая общая подпоследовательность
3. Способы реализовать динамику
1. Вперед [code]
2. Назад [code-1] [code-2]
3. Лениво (рекурсивно) [code]
4. Случай когда ленивость улучшает: минимальное по весу паросочетание [text]
4. Восстановление ответа
1. Храним весь ответ [code]
2. Храним ссылку назад [code] [bits]
3. Ничего не храним [code]
5. Оптимизация по памяти
1. Храним только две строки, копируем [code]
2. А теперь не копируем [code]
3. А теперь все по модулю два [code]
6. Рекурсия и доминошки
1. Рекурсия [code]
2. Запоминание, изломанный профиль [code]
7. Интересные приемы
1. Задача о возрастающей подпоследовательности
1. len[i]
2. len[i,j], x=a[j]
3. [i, x, len]
4. x[i, len], x_i → x_i+1
2. Задача про погрузку грузов (можно брать вещи с двух концов последовательности, в ящик помещается W, минимизировать кол-во ящиков)
1. 2 3 4 5 6 7, W = 9 : 2+3+5 = Wrong Way, 2+7, 3+6, 4+5 = 3 ящика
2. Решение за O(n⁵) k[L, R] → [a, b]
3. Решение за O(n³) k[L, R] → [a, b], где b = min возможный
4. Решение за O(n²) [a, b, k, w] : pair(k, w) [a, b]
5. Оптимизация памяти до линии