Динамическое программирование:Тикеты — различия между версиями
(→1 Классические задачи динамического программирования) |
м (→1 Классические задачи динамического программирования) |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 3: | Строка 3: | ||
=== 1 Классические задачи динамического программирования === | === 1 Классические задачи динамического программирования === | ||
# [[Кратчайший путь в ациклическом графе]] | # [[Кратчайший путь в ациклическом графе]] | ||
| − | # [[Задача о числе путей в ациклическом графе]] | + | # [[Задача о числе путей в ациклическом графе]] |
| − | + | # [[Задача о расстановке знаков в выражении]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # [[Задача о расстановке знаков в выражении]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Задача о порядке перемножения матриц]] (3) | # [[Задача о порядке перемножения матриц]] (3) | ||
## Взять переменные и константы в Tex | ## Взять переменные и константы в Tex | ||
| Строка 33: | Строка 18: | ||
# [[Задача коммивояжера, ДП по подмножествам]] | # [[Задача коммивояжера, ДП по подмножествам]] | ||
# [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]] | # [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]] | ||
| − | # | + | # [[Задача о рюкзаке]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
=== 2 Способы оптимизации методов динамического программирования === | === 2 Способы оптимизации методов динамического программирования === | ||
Версия 19:56, 23 сентября 2017
Содержание
Динамическое программирование
0 Динамическое программирование
1 Классические задачи динамического программирования
- Кратчайший путь в ациклическом графе
- Задача о числе путей в ациклическом графе
- Задача о расстановке знаков в выражении
- Задача о порядке перемножения матриц (3)
- Взять переменные и константы в Tex
- Обернуть задачу в шаблон
- Интервики на конспект правильных скобочных последовательностей
- Написать, почему нас не устраивает число Каталана в асимптотике
- Отформатировать псевдокоды
- Оформить правильно источники информации
- Убрать про мемоизацию
- Задача о наибольшей общей подпоследовательности
- Задача о наибольшей возрастающей подпоследовательности
- Быстрый поиск наибольшей возрастающей подпоследовательности*
- Задача коммивояжера, ДП по подмножествам
- Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
- Задача о рюкзаке
2 Способы оптимизации методов динамического программирования
- Метод четырех русских для умножения матриц
- Применение метода четырех русских в задачах ДП на примере задачи о НОП
- Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
- Meet-in-the-middle
- Convex hull trick
3 Другие задачи
- Задача о расстоянии Дамерау-Левенштейна
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о наибольшей подпоследовательности-палиндроме
- Задача о наибольшей общей возрастающей последовательности
- Задача о наибольшей общей палиндромной подпоследовательности
- Динамическое программирование по профилю (7)
- Англоязычные термины
- Заменить умножение на \cdot
- Заменить дефисы на тире
- Взять переменные и константы в Tex
- Отформатировать псевдокоды
- Добавить ещё примеров
- Оформить правильно источники информации
- Добавить нормальное объяснение происходящего (и почему это работает)
- Динамика по поддеревьям
