Динамическое программирование:Тикеты

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

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

1 Классические задачи динамического программирования

1. Кратчайший путь в ациклическом графе
2. Задача о числе путей в ациклическом графе (4)
   1. Взять задачу в шаблон
   2. Отформатировать псевдокод
   3. Обернуть имя функции в тексте в mathrm
   4. Заменить дефисы на тире
   5. Добавить см. также и источники информации
   6. Добавить пример простого ациклического графа в виде прямоугольной матрицы с препятствиями
3. Задача о расстановке знаков в выражении (6)
   1. Взять задачу в шаблон
   2. Исправить знаки неравенств
   3. Ссылку примечанием оформить нормально
   4. Взять все переменные и константы в тексте в Tex
   5. Отформатировать псевдокод
   6. Табличку нормально оформить
   7. Описать восстановление ответа
   8. Источники информации правильно оформить
   9. Добавить решение задачи без возможности использования скобок
4. Задача о порядке перемножения матриц (3)
   1. Взять переменные и константы в Tex
   2. Обернуть задачу в шаблон
   3. Интервики на конспект правильных скобочных последовательностей
   4. Написать, почему нас не устраивает число Каталана в асимптотике
   5. Отформатировать псевдокоды
   6. Оформить правильно источники информации
   7. Убрать про мемоизацию
5. Задача о наибольшей общей подпоследовательности
6. Задача о наибольшей возрастающей подпоследовательности
7. Быстрый поиск наибольшей возрастающей подпоследовательности*
8. Задача коммивояжера, ДП по подмножествам
9. Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
10. Задача о рюкзаке (8)
    1. Взять задачу в шаблон
    2. Отформатировать псевдокоды
    3. Заменить дефисы на тире
    4. Исправить знаки неравенств
    5. Написать, что метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время и написать почему
    6. Сделать итоговую формулу для А c помощью фигурной скобки
    7. Предложить вариант замены картинок на вики-таблички с сохранением обозначения пути
    8. Понизить уровень заголовков первого уровня
    9. Оформить правильно источники информации

2 Способы оптимизации методов динамического программирования

1. Метод четырех русских для умножения матриц
2. Применение метода четырех русских в задачах ДП на примере задачи о НОП[math]^\star[/math]
3. Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
4. Meet-in-the-middle[math]^\star[/math]
5. Convex hull trick

3 Другие задачи

1. Задача о расстоянии Дамерау-Левенштейна[math]^\star[/math]
2. Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
3. Задача о наибольшей подпоследовательности-палиндроме
4. Задача о наибольшей общей возрастающей последовательности[math]^\star[/math]
5. Задача о наибольшей общей палиндромной подпоследовательности[math]^\star[/math]
6. Динамическое программирование по профилю (7)
   1. Англоязычные термины
   2. Заменить умножение на \cdot
   3. Заменить дефисы на тире
   4. Взять переменные и константы в Tex
   5. Отформатировать псевдокоды
   6. Добавить ещё примеров
   7. Оформить правильно источники информации
   8. Добавить нормальное объяснение происходящего (и почему это работает)
7. Динамика по поддеревьям