Динамическое программирование: Фибоначчи, рюкзак и мемоизация

Коротко: Динамическое программирование решает задачи с перекрывающимися подзадачами, сохраняя промежуточные результаты вместо их повторного вычисления; так экспоненциальные вычисления становятся полиномиальными.

Подробнее: Если рекурсивное решение снова и снова решает одни и те же подзадачи, результаты сохраняют. Два способа: мемоизация (сверху вниз: рекурсия + кеш) и табуляция (снизу вверх: заполнение таблицы).