Что такое динамическое программирование?

Динамическое программирование (ДП) — это метод решения сложных вычислительных задач путем разбиения их на более простые подзадачи. Результаты решения этих подзадач сохраняются (мемоизация или табуляция) во избежание повторных вычислений. Это позволяет значительно оптимизировать производительность по сравнению с наивными рекурсивными решениями.

Основные принципы:

• Перекрывающиеся подзадачи: Одна и та же подзадача должна решаться многократно при решении исходной задачи.
• Оптимальная подструктура: Оптимальное решение исходной задачи может быть получено из оптимальных решений ее подзадач.

Два основных подхода:

1. Нисходящий (сверху вниз): Применяется рекурсия с мемоизацией. Задача разбивается на подзадачи, и их решения запоминаются в словаре или массиве.
2. Восходящий (снизу вверх): Используется итеративный подход с табуляцией. Решения подзадач вычисляются в определенном порядке (обычно от меньших к большим) и сохраняются в таблице.

Пример. Задача о числе Фибоначчи:

Наивное рекурсивное решение (без ДП):

def fibonacci_naive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_naive(n - 1) + fibonacci_naive(n - 2) # Повторные вычисления одного и того же значения

Решение с ДП (мемоизация):

def fibonacci_memoization(n, memo={}):
    if n in memo:
        return memo[n] # Возвращаем сохраненный результат
    if n <= 1:
        return n
    else:
        result = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo)
        memo[n] = result # Сохраняем результат
        return result

Решение с ДП (табуляция):

def fibonacci_tabulation(n):
    if n <= 1:
        return n
    
    dp = [0] * (n + 1) # Таблица для хранения результатов
    dp[0] = 0
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] # Вычисляем результат на основе предыдущих

    return dp[n]

Различия между мемоизацией и табуляцией:

Параметр	Мемоизация (Нисходящий)	Табуляция (Восходящий)
Подход	Рекурсивный	Итеративный
Порядок	Вычисления в зависимости от запроса	Вычисления в предопределенном порядке
Память	Может использовать больше памяти (стек)	Обычно использует фиксированный массив/таблицу
Реализация	Может быть проще для некоторых задач	Обычно более эффективна по памяти и скорости

ДП применяется в различных областях, включая:

• Оптимизация: задача о рюкзаке, задача коммивояжера.
• Биоинформатика: выравнивание последовательностей ДНК.
• Компьютерное зрение: распознавание образов.
• Финансы: планирование инвестиций.