# [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] 0.25
## См. также
== 7 Динамическое программирование ==
0 [[Динамическое программирование]]
=== 1 Классические задачи динамического программирования ===
# [[Кратчайший путь в ациклическом графе]]
# [[Задача о числе путей в ациклическом графе]] (4)
## Взять задачу в шаблон
## Отформатировать псевдокод
## Обернуть имя функции в тексте в mathrm
## Заменить дефисы на тире
## Добавить см. также и источники информации
## Добавить пример простого ациклического графа в виде прямоугольной матрицы с препятствиями
# [[Задача о расстановке знаков в выражении]] (6)
## Взять задачу в шаблон
## Исправить знаки неравенств
## Ссылку примечанием оформить нормально
## Взять все переменные и константы в тексте в Tex
## Отформатировать псевдокод
## Табличку нормально оформить
## Описать восстановление ответа
## Источники информации правильно оформить
## Добавить решение задачи без возможности использования скобок
# [[Задача о порядке перемножения матриц]] (3)
## Взять переменные и константы в Tex
## Обернуть задачу в шаблон
## Интервики на конспект правильных скобочных последовательностей
## Написать, почему нас не устраивает число Каталана в асимптотике
## Отформатировать псевдокоды
## Оформить правильно источники информации
## Убрать про мемоизацию
# [[Задача о наибольшей общей подпоследовательности]]
# [[Задача о наибольшей возрастающей подпоследовательности]]
# [[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
# [[Задача коммивояжера, ДП по подмножествам]]
# [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
# [[Задача о рюкзаке]] (8)
## Взять задачу в шаблон
## Отформатировать псевдокоды
## Заменить дефисы на тире
## Исправить знаки неравенств
## Написать, что метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время и написать почему
## Сделать итоговую формулу для А c помощью фигурной скобки
## Предложить вариант замены картинок на вики-таблички с сохранением обозначения пути
## Понизить уровень заголовков первого уровня
## Оформить правильно источники информации
=== 2 Способы оптимизации методов динамического программирования ===
# [[Метод четырех русских для умножения матриц]]
# [[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
# [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
# [[Meet-in-the-middle]]<tex>^\star</tex>
# [[Convex hull trick]]
=== 3 Другие задачи ===
# [[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
# [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
# [[Задача о наибольшей подпоследовательности-палиндроме]]
# [[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
# [[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
# [[Динамическое программирование по профилю]] (7)
## Англоязычные термины
## Заменить умножение на \cdot
## Заменить дефисы на тире
## Взять переменные и константы в Tex
## Отформатировать псевдокоды
## Добавить ещё примеров
## Оформить правильно источники информации
## Добавить нормальное объяснение происходящего (и почему это работает)
# [[Динамика по поддеревьям]]
