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

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

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

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

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 июня. Записаться на него можно по ссылке.