Динамическое программирование в Python: от теории к практике
Динамическое программирование в Python: от теории к практике
Динамическое программирование (ДП) — это мощный метод оптимизации, используемый для решения задач путем разбиения их на перекрывающиеся подзадачи. В этой статье мы разберем основы ДП, его типы и реализацию в Python с примерами.
Что такое динамическое программирование?
Динамическое программирование применяется для задач, где решение можно выразить через решения меньших подзадач. Основные принципы:
- Оптимальная подструктура: оптимальное решение задачи включает оптимальные решения подзадач.
- Перекрывающиеся подзадачи: одни и те же подзадачи решаются многократно.
Типы динамического программирования
- Сверху вниз (Top-Down)
Рекурсивный подход с мемоизацией (кэшированием результатов). - Снизу вверх (Bottom-Up)
Итеративный подход с заполнением таблицы результатов от простых к сложным.
Пример 1: Числа Фибоначчи
Классический пример перекрывающихся подзадач.
Наивная рекурсия (неэффективно)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
Сложность: O(2ⁿ) из-за повторных вычислений.
Решение с мемоизацией (Top-Down)
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
Сложность: O(n).
Итеративное решение (Bottom-Up)
def fib_tab(n):
if n == 0:
return 0
table = [0] * (n+1)
table[1] = 1
for i in range(2, n+1):
table[i] = table[i-1] + table[i-2]
return table[n]
Сложность: O(n), память: O(n).
Пример 2: Задача о рюкзаке
Задача: выбрать предметы с максимальной суммарной стоимостью без превышения веса рюкзака.
Решение ДП (Bottom-Up)
def knapsack(weights, values, capacity):
n = len(values)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i-1] > w:
dp[i][w] = dp[i-1][w]
else:
dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])
return dp[n][capacity]
# Пример использования
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity)) # Вывод: 7 (предметы 2 и 3)
Сложность: O(n * capacity).
Советы по применению ДП
- Определите, обладает ли задача оптимальной подструктурой.
- Проверьте наличие перекрывающихся подзадач.
- Выберите подход: Top-Down (проще для рекурсивных задач) или Bottom-Up (эффективнее по памяти).
- Используйте мемоизацию через декоратор
@lru_cacheдля упрощения кода:from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2)
Ограничения ДП
- Высокие требования к памяти для таблиц.
- Не все задачи можно разбить на перекрывающиеся подзадачи.
Заключение
Динамическое программирование — ключевой инструмент для оптимизации задач в Python. Практикуйтесь на задачах:
- Наибольшая общая подпоследовательность.
- Размен монет.
- Редакционное расстояние (Левенштейна).
Дополнительные ресурсы:
- Книга «Алгоритмы. Построение и анализ» (Кормен и др.).
- Курс «Grokking Dynamic Programming Patterns» на Educative.