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

Разбиваем задачу на подзадачи меньшего размера.

Условно методы ДП можно поделить на два класса:
1. Деление пополам (например, сортировка массива слиянием).
2. Сохранение результатов вычисления подзадач (например, вычисление чисел Фибоначчи).

Есть два способа вычисления результатов подзадач - сверху вниз и снизу вверх. Обычно, но не всегда, сверху вниз проще придумать, но снизу вверх работает быстрее (при той же вычислительной сложности).

Пример:
Сортировка массива.
Сверху вниз. Делим массив пополам, сортируем каждую половину отдельно, сливаем результаты.
Снизу вверх. Делим массив из эн элементов на эн массивов из 1 элемента. Сливаем попарно соседние массивы.

1