Динамика (11 ноября 2019)

  1. Динамика, вводная
    1. Числа Фибоначчи (уже везде видели). C(n,k) (считали на последней практике).
    2. Кратчайшая последовательность прыжков кролика x → x+3...x+5 так, что кролик не попадает в дырку.
    3. Кратчайшая последовательность операций из 1 получить N ≤ 106, операции: x → x+1,x+7,2x,3x.
    4. Вперед
    5. Назад
    6. Рекурсивно-ленивая
    7. Задача про путь "на матрице с дыркам": sum → max кол-во способов
    8. Задача про путь "на матрице с дыркам": можно хранить путь до состояния, можно от состояния
    9. Восстановление ответа, 2 способа: или храним ссылки между состояниями, или не храним
    10. Граф динамики: состояния, переходы, вперед (исходящие рёбра), назад (входящие рёбра), ленивая (только достижимые состояния)
    11. Что нужно, чтобы решить задачу динамикой? Список: состояние динамики, переходы между состояниями, начальное состояние, конечное состояние, порядок пересчёта.
− Перерыв −
  1. Рюкзак (без стоимостей!!!)
    1. Условие: даны вещи, у них есть веса, выбрать подмножества суммарного веса ровно W
    2. is[i, w i] (w − вес, i − префикс)
    3. is[w] (хранить только последнюю строку)
    4. bitset<W> реализация на bitset-ах (просто показать bitset, подробный рассказ на следующей лекции)
    5. last[w], восстановление ответа с линейной памятью

  2. НОП, НВП, Левинштейн
    1. Условие: даны две последовательности, выбрать наибольшую общую подпоследовательность
    2. Решение: f[i,j] − длина НОП для s[:i], t[:j] (только за квадрат!!!)
    3. НВП за n2
    4. [skipped] Расстояние Левенштейна за n2 (будет на практике!)
    5. [skipped] Сведения: НВП <−> НОП (будет в ДЗ!)

  3. [skipped] Бонус: как НОП считать быстро? про diff. или считать окно длины 100, или НОП → НВП.
  4. [skipped] Бонус: как Левенштейна применить к распознаванию речи?

  5. НОП: оптимизация памяти
    1. Оптимизация памяти: без восстановления ответа храним только 2 строки
    2. Оптимизация памяти: с восстановлением ответа храним только bitset<N> f[N];
    3. Оптимизация памяти: алгоритм Хиршберга
    4. Область применения хиршберга: расстояние Левенштейна, любая задача монотонная по обеим координатам