Динамическое программирование на Python

Привет, Хабр!

Динамическое программирование полезно при решении оптимизационных задач и задач на вычисление, где присутствует большое количество повторяющихся подзадач.

По сравнению с другими алгоритмическими подходами, динамическое программирование позволяет ускорить процесс вычисления за счет сохранения результатов выполнения подзадач.

Основные идеи динамического программирования:

1. Переиспользование решений подзадач: основа динамического программирования — это использование уже найденных решений подзадач, чтобы построить решение для более крупной задачи.

2. Мемоизация: техника, при которой результаты выполнения функций сохраняются и повторно используются при последующих вызовах с теми же входными данными, предотвращая ненужные вычисления.

3. Табуляция: метод, при котором решение задачи строится «снизу вверх», т. е. сначала вычисляются решения для всех малых подзадач, а затем они комбинируются для решения более крупных задач.

Динамическое программирование на 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)}")

---

Для того, чтобы писать качественные и «шустрые» приложения, недостаточно выучить язык программирования. Вам нужно чётко понимать, каким образом ваш код преобразуется в инструкции для центрального процессора. Этой непростой теме — компиляции — посвящён открытый урок, который пройдет в Otus 13 июня. Записаться на него можно по ссылке.