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

Коротко: Динамічне програмування розв’язує задачі з підзадачами, що перекриваються, зберігаючи проміжні результати замість їх повторного обчислення; так експоненційні обчислення стають поліноміальними.

Докладніше: Якщо рекурсивний розв’язок знову і знову розв’язує одні й ті самі підзадачі, результати зберігають. Два способи: мемоїзація (згори донизу: рекурсія + кеш) і табуляція (знизу догори: заповнення таблиці).