Решил сформировать список паттернов для решения алгоритмических задач плюс примеры задач на каждый паттерн. Оказывается, то что я для себя называл Нарастающая сумма - правильно называется Динамическое программирование.

Такого определения динамического программирования, чтобы мне понравилось, не нашёл. Лучший вариант “Динамические алгоритмы делят задачу на кусочки и вычисляют их по очереди, шаг за шагом наращивая решения. Поэтому динамические алгоритмы можно представить как рекурсию, работающую снизу вверх”, ну или как я формулирую для себя - по принципу нарастающей суммы. Находим решение для минимальной конфигурации, и, далее, добавляем элементы по одному и находим решение, используя результаты предыдущего шага, пока не обработаем все.

Примеры задач

Самая длинная возрастающая подпоследовательность

Минимальная сумма нисходящего пути

Подъём по лестнице

Максимальная прибыль от планирования работ