Привет, Хабр!
Динамическое программирование полезно при решении оптимизационных задач и задач на вычисление, где присутствует большое количество повторяющихся подзадач.
По сравнению с другими алгоритмическими подходами, динамическое программирование позволяет ускорить процесс вычисления за счет сохранения результатов выполнения подзадач.
Основные идеи динамического программирования:
Переиспользование решений подзадач: основа динамического программирования — это использование уже найденных решений подзадач, чтобы построить решение для более крупной задачи.
Мемоизация: техника, при которой результаты выполнения функций сохраняются и повторно используются при последующих вызовах с теми же входными данными, предотвращая ненужные вычисления.
Табуляция: метод, при котором решение задачи строится «снизу вверх», т. е. сначала вычисляются решения для всех малых подзадач, а затем они комбинируются для решения более крупных задач.
Динамическое программирование на Python
В основном динамическое программированиена Python реализуется с помощью рекурсии, мемоизации и табулирования.
Рекурсия — это метод, при котором функция вызывает сама себя. Однако рекурсия иногда может быть неэффективной из-за многократных вызовов с одинаковыми параметрами.
Рассмотрим классическую задачу вычисления чисел Фибоначчи. Простой рекурсивный метод может выглядеть так:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)Метод хоть и понятный, но очень неэффективен для больших n из-за экспоненциального времени выполнения.
Мемоизация юзают для ускорения программ путем хранения результатов дорогостоящих функциональных вызовов и повторного использования их, когда те же самые входы встречаются снова.
Python позволяет использовать декораторы для мемоизации. Например, для мемоизации функции Фибоначчи код будет таким:
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci(n):
if n < 2:
return n
return fibonacci(n-1) + fibonacci(n-2)lru_cache — это декоратор, который автоматически хранит результаты вызовов функции и предоставляет их при последующих вызовах с теми же аргументами.
Табулирование — это метод, при котором проблема решается снизу вверх. Строим таблицу, которая хранит результаты всех подзадач, начиная с базовых случаев и заканчивая решением основной задачи. В отличие от мемоизации в табулировании сначала заполняем всю таблицу, а затем используем её для получения ответа.
Рассмотрим классическую задачу вычисления n-го числа Фибоначчи.
Последовательность Фибоначчи определяется следующим образом:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2), где n > 1
С табулированием можно избежать повторных вычислений:
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
# инициализация таблицы с базовыми случаями
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]
# пример
n = 10
print(f"Fibonacci({n}) = {fibonacci(n)}")Инициализируем таблицу для хранения промежуточных результатов с размером n+1n+1n+1.
Устанавливаем базовые случаи F(0)=0F(0) = 0F(0)=0 и F(1)=1F(1) = 1F(1)=1.
Используем цикл для вычисления значений Фибоначчи от F(2)F(2)F(2) до F(n)F(n)F(n) и сохраняем их в таблице.
Возвращаем значение F(n)F(n)F(n).
Так можно достичь временной сложности O(n)O(n)O(n), избегая экспоненциального роста времени выполнения, присущего наивному рекурсивному подходу.
Стандартные задачи
Задача о рюкзаке
Задача заключается в выборе подмножества предметов с заданными весами и ценностями, чтобы максимизировать общую ценность, не превышая заданного ограничения по весу.
Решение:
def knapsack(weights, values, capacity):
n = len(values)
memo = [[-1 for _ in range(capacity + 1)] for _ in range(n + 1)]
def knapsack_rec(w, i):
if i == 0 or w == 0:
return 0
if memo[i][w] != -1:
return memo[i][w]
if weights[i - 1] <= w:
memo[i][w] = max(values[i - 1] + knapsack_rec(w - weights[i - 1], i - 1), knapsack_rec(w, i - 1))
else:
memo[i][w] = knapsack_rec(w, i - 1)
return memo[i][w]
return knapsack_rec(capacity, n)
weights = [1, 2, 3, 4]
values = [10, 20, 30, 40]
capacity = 5
print(knapsack(weights, values, capacity))Основная суть решения заключается в хранении результатов подзадач в матрице memo, чтобы избежать повторных вычислений.
Задача о наибольшей общей подпоследовательности
Задача LCS заключается в нахождении самой длинной последовательности, которая является подпоследовательностью двух заданных строк.
Решение с мемоизацией:
def lcs(X, Y):
m = len(X)
n = len(Y)
memo = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]
def lcs_rec(i, j):
if i == 0 or j == 0:
return 0
if memo[i][j] != -1:
return memo[i][j]
if X[i - 1] == Y[j - 1]:
memo[i][j] = 1 + lcs_rec(i - 1, j - 1)
else:
memo[i][j] = max(lcs_rec(i - 1, j), lcs_rec(i, j - 1))
return memo[i][j]
return lcs_rec(m, n)
X = "AGGTAB"
Y = "GXTXAYB"
print(lcs(X, Y))Храним результаты подзадач в матрице memo. Так можно ускорить вычисления за счет устранения повторных вызовов с одинаковыми параметрами.
Задача о наибольшей возрастающей подпоследовательности
Задача заключается в нахождении самой длинной возрастающей подпоследовательности в заданном массиве чисел.
Решение с мемоизацией:
def lis(arr):
n = len(arr)
memo = [-1] * n
def lis_rec(i):
if memo[i] != -1:
return memo[i]
max_ending_here = 1
for j in range(i):
if arr[j] < arr[i]:
max_ending_here = max(max_ending_here, lis_rec(j) + 1)
memo[i] = max_ending_here
return max_ending_here
max_lis = 1
for i in range(1, n):
max_lis = max(max_lis, lis_rec(i))
return max_lis
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print(lis(arr))Задача о разбиении строки
Задача заключается в определении, можно ли разбить строку на последовательность одного или более слов из словаря. Решение:
def word_break(s, word_dict):
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_dict:
dp[i] = True
break
return dp[len(s)]
s = "leetcodeotus"
word_dict = {"leet", "code", "otus"}
print(f"Can the string be segmented: {word_break(s, word_dict)}")Чтобы узнать свой уровень знания Python и оценить, потянете ли вы программу курса «Python Developer. Professional», пройдите вступительный тест.
Также рекомендуем ознакомиться с каталогом курсов по программированию, где собраны обучающие программы по технологиям и практикам, востребованные в индустрии.
Чтобы оставаться в курсе самых актуальных технологий и трендов, подписывайтесь на Telegram-канал OTUS.