Динамическое программирование
Динамическое программирование (DP) — метод решения задач путём разбиения их на подзадачи и сохранения результатов для избежания повторных вычислений.
- Рекурсивный подход с кэшированием результатов
- Реализуется через декораторы или словари
- В Python:
@lru_cache декоратор
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
- Итеративный подход, заполнение таблицы от базовых случаев к целевому решению
- Часто более эффективна по памяти и избегает проблем с глубиной рекурсии
def fibonacci(n):
if n <= 1:
return n
dp = [0, 1]
for i in range(2, n+1):
dp.append(dp[i-1] + dp[i-2])
return dp[n]
- Базовый случай: F(0) = 0, F(1) = 1
- Рекуррентное соотношение: F(n) = F(n-1) + F(n-2)
- Сложность без DP: O(2ⁿ), с DP: O(n)
Задача о рюкзаке (Knapsack)
- Цель: максимизировать стоимость предметов при ограничении веса
- Подзадачи: максимальная стоимость для первого i предметов и вместимости w
- Сложность: O(n × W), где n — количество предметов, W — вместимость
Наибольшая общая подпоследовательность (LCS)
- Цель: найти длину наибольшей общей подпоследовательности двух строк
- Подзадачи: LCS для префиксов строк
- Сложность: O(m × n), где m, n — длины строк
Практические рекомендации
-
- Задача имеет оптимальную подструктуру (оптимальное решение состоит из оптимальных решений подзадач)
- Задача имеет перекрывающиеся подзадачи (одни и те же подзадачи решаются многократно)
-
- Мемоизация: проще в реализации, интуитивно понятна
- Табуляция: эффективнее по памяти, избегает stack overflow
-
- Используйте только необходимые состояния (space optimization)
- Для больших значений рассмотрите матричное возведение в степень (для линейных рекуррентных соотношений)
- Учитывайте границы задачи для оптимизации размера таблицы
-
- Забыть базовый случай в рекурсии
- Неправильное определение подзадач
- Не учитывать все возможные переходы между состояниями