Подсказка 1: задача состоит из похожих подзадач
Если задача разбивается на несколько маленьких подзадач, которые очень похожи друг на друга, значит, скорее всего, её можно решить с помощью динамического программирования.
Это похоже на математическую индукцию:
- мы знаем, как решить задачу в самом начале,
- если умеем решать её на шаге k, значит, сможем решить и на шаге k + 1,
- а значит, умеем решать её на любом шаге!
Подсказка 2: начальные шаги известны
Возьмём последовательность Фибоначчи:
- мы знаем, что f₁ = 1 и f₂ = 1,
- зная два числа, легко посчитать третье: f₃ = f₁ + f₂,
- затем f₄, f₅ и так до нужного fₙ.
Чтобы найти, например, 10-е число, достаточно пройти все шаги от 1 до 10.
Подсказка 3: маленькие задачи легко решать
Если каждая подзадача решается простым действием (например, сложить два числа), значит динамика подойдёт.
В Фибоначчи это очень наглядно: на каждом шаге всего лишь сложение.
Подсказка 4: можно хранить результаты в таблице
Главная идея динамики: мы ничего не пересчитываем заново.
Мы просто запоминаем результаты маленьких шагов и используем их для следующего.
Например, для Фибоначчи можно хранить:
f₁ = 1
f₂ = 1
f₃ = 2
f₄ = 3
f₅ = 5
...И на каждом шаге брать уже готовые значения.
Выводы
Динамическое программирование — это не волшебная палочка.
- Иногда нужен полный перебор (brute force),
- иногда лучше подойдёт жадный алгоритм,
- а иногда достаточно рекурсии с мемоизацией.
Но если удаётся применить динамическое программирование, оно часто помогает получить быстрое и понятное решение.