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

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

📌 Про що ця тема

Динамічне програмування (ДП) — це метод розв'язання задач, коли велику задачу розбивають на менші підзадачі, розв'язують кожну один раз і зберігають результати, щоб не рахувати їх повторно. На іспиті перевіряють розуміння ідеї ДП, уміння відрізнити його від рекурсії «в лоб», оцінити складність і впізнати типові задачі.

📖 Головне

• ДП застосовне, коли задача має дві властивості: оптимальна підструктура (розв'язок задачі будується з розв'язків підзадач) та перекривання підзадач (ті самі підзадачі зустрічаються багато разів).

• Ключова ідея — мемоізація: зберігати вже обчислені відповіді в масиві/таблиці, щоб кожну підзадачу рахувати лише раз.

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

• Складність зазвичай = (кількість різних підзадач) × (час обробки однієї підзадачі). Часто це значно швидше за повний перебір чи «голу» рекурсію.

• Проста рекурсія для чисел Фібоначчі має складність O(2^n) через повторні обчислення; з ДП — O(n).

• Класичні задачі ДП: числа Фібоначчі, задача про рюкзак, найдовша спільна підпослідовність, кількість шляхів у сітці, розмін монет, сходинки.

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

🔢 Як це працює на прикладі

Задача: скількома способами піднятись на n сходинок, якщо за крок робимо 1 або 2 сходинки?

• Підзадача: f(k) — кількість способів дійти до сходинки k.

• Рекурентність: f(k) = f(k-1) + f(k-2), бо на k-ту сходинку потрапляємо або з (k-1), або з (k-2).

• База: f(0) = 1, f(1) = 1.

• Таблиця для n=5: f(0)=1, f(1)=1, f(2)=2, f(3)=3, f(4)=5, f(5)=8.

• Відповідь: 8 способів. Кожне значення обчислено один раз — складність O(n).

⚠️ Типові помилки

• Плутають ДП із простою рекурсією: без збереження результатів це не ДП, а звичайний (повільний) перебір.

• Неправильно задають базу рекурентності — через це вся таблиця рахується з помилкою.

• Плутають ДП із жадібним алгоритмом: жадібний не завжди дає оптимум (напр., у розміні монет нестандартними номіналами).

• Невірно оцінюють складність: забувають помножити кількість підзадач на вартість обробки однієї.

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

🎯 Що завчити напам'ять

• Дві умови застосовності: оптимальна підструктура + перекривання підзадач.

• Два підходи: згори вниз (мемоізація) і знизу вгору (табличний).

• Фібоначчі: рекурсія O(2^n), ДП O(n).

• Складність ДП = число підзадач × вартість однієї підзадачі.

• ДП ≠ жадібний: ДП перебирає, жадібний бере локально найкраще.

🧠 Перевір себе

1. Які дві властивості задачі потрібні для застосування ДП?

2. Чим мемоізація відрізняється від звичайної рекурсії?

3. Яка складність обчислення чисел Фібоначчі з ДП?

4. Скільки способів піднятися на 4 сходинки (кроки 1 або 2)?

Відповіді: 1 — оптимальна підструктура і перекривання підзадач; 2 — мемоізація зберігає обчислені результати підзадач, тож кожна рахується лише раз; 3 — O(n); 4 — 5 способів.