Алгоритмы
Динамическое программирование
Цели урока
- Понять парадигму DP
- Освоить 5 шагов решения
- Решать 1D и 2D задачи
- Оптимизировать память
Предварительные знания
- Divide and Conquer
90% задач на алгоритмических интервью решаются DP. Это не магия - это техника: определи состояние, напиши рекуррентность, найди ответ.
- Автокоррекция (edit distance)
- Git diff (LCS)
- Биоинформатика (выравнивание последовательностей)
- Финансы (оптимальные стратегии)
Ричард Беллман и название, спрятавшее математику
Динамическое программирование придумал Ричард Беллман в корпорации RAND в начале 1950-х. У названия есть знаменитая история, которую Беллман рассказал в автобиографии. RAND работала на ВВС, а министр обороны Чарльз Уилсон открыто не любил математические исследования. Беллману нужно было название для работы о многошаговых процессах принятия решений, которое не звучало бы как математика. Он выбрал слово «динамическое», потому что оно звучало активно и его нельзя было использовать в уничижительном смысле, и «программирование», которое тогда означало планирование и составление расписаний, а не написание кода. Главная идея, это принцип оптимальности: оптимальное решение строится из оптимальных решений подзадач, а перекрывающиеся подзадачи решаются один раз и сохраняются. Это объединило огромный класс задач оптимизации, от кратчайших путей до управления запасами.
Идея: подзадачи + мемоизация
**Dynamic Programming (DP)** = разбиение на подзадачи + запоминание результатов.
**Решение DP:** запоминаем уже вычисленные значения.
**DP vs D&C:** в D&C подзадачи независимы. В DP подзадачи перекрываются (one computes same subproblem many times).
fib(50) наивной рекурсией выполнит ~2^50 ≈ 10^15 операций. С DP?
Подход к DP задачам
**Пример: Coin Change**
**Главный вопрос:** «Какая информация нужна, чтобы принять решение?» Это определяет состояние.
Для задачи «количество способов набрать сумму монетами» что меняется?
1D DP: классика
**1. Climbing Stairs (лестница):**
**2. House Robber (грабитель):**
**3. Longest Increasing Subsequence (LIS):**
House Robber: nums = [2, 7, 9, 3, 1]. Ответ?
2D DP: таблицы
**1. 0/1 Knapsack (рюкзак):**
**2. Longest Common Subsequence (LCS):**
**3. Edit Distance (расстояние редактирования):**
**Оптимизация памяти:** часто можно хранить только 2 строки (текущую и предыдущую) вместо всей таблицы.
Edit distance("kitten", "sitting") = ?
Dynamic Programming
- Подзадачи + мемоизация
- 5 шагов: State, Recurrence, Base, Order, Answer
- Top-down (рекурсия + memo) vs Bottom-up (таблица)
- 1D: O(n), 2D: O(n×m)
- Часто можно оптимизировать память
Связанные темы
DP - одна из главных парадигм.
- Greedy — Когда подзадачи независимы
- Divide & Conquer — Без перекрытия подзадач
Связанные уроки
- alg-19-divide-conquer — DP - это разделяй и властвуй с перекрывающимися подзадачами
- alg-20-greedy — Жадность решает локально; DP перебирает все подзадачи
- alg-28-lcs — LCS - канонное применение 2D DP
- alg-30-knapsack — Рюкзак - модельная задача оптимизации через DP
- la-09-systems — Уравнения Беллмана решают динамическую оптимизацию через DP
- comp-23-local-optimization
- comp-25-loop-optimizations
- plt-27-ir-optimization
- ml-36-seq2seq