Динамічне програмування

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

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

Подробиці

Приклад: розмін монет

Яка мінімальна кількість…

Див. також: мемоїзація, рекурсія, алгоритми, О-нотація