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

#Основные концепции

Динамическое программирование (DP) — метод решения задач путём разбиения их на подзадачи и сохранения результатов для избежания повторных вычислений.

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

#1. Мемоизация (Top-down)

Рекурсивный подход с кэшированием результатов
Реализуется через декораторы или словари
В Python: @lru_cache декоратор

Пример:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

#2. Табуляция (Bottom-up)

Итеративный подход, заполнение таблицы от базовых случаев к целевому решению
Часто более эффективна по памяти и избегает проблем с глубиной рекурсии

Пример:

def fibonacci(n):
    if n <= 1:
        return n
    dp = [0, 1]
    for i in range(2, n+1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]

#Классические задачи DP

#Задача Фибоначчи

Базовый случай: F(0) = 0, F(1) = 1
Рекуррентное соотношение: F(n) = F(n-1) + F(n-2)
Сложность без DP: O(2ⁿ), с DP: O(n)

#Задача о рюкзаке (Knapsack)

Цель: максимизировать стоимость предметов при ограничении веса
Подзадачи: максимальная стоимость для первого i предметов и вместимости w
Сложность: O(n × W), где n — количество предметов, W — вместимость

#Наибольшая общая подпоследовательность (LCS)

Цель: найти длину наибольшей общей подпоследовательности двух строк
Подзадачи: LCS для префиксов строк
Сложность: O(m × n), где m, n — длины строк

#Практические рекомендации

Когда использовать DP
- Задача имеет оптимальную подструктуру (оптимальное решение состоит из оптимальных решений подзадач)
- Задача имеет перекрывающиеся подзадачи (одни и те же подзадачи решаются многократно)
Выбор подхода
- Мемоизация: проще в реализации, интуитивно понятна
- Табуляция: эффективнее по памяти, избегает stack overflow
Оптимизации
- Используйте только необходимые состояния (space optimization)
- Для больших значений рассмотрите матричное возведение в степень (для линейных рекуррентных соотношений)
- Учитывайте границы задачи для оптимизации размера таблицы
Типичные ошибки
- Забыть базовый случай в рекурсии
- Неправильное определение подзадач
- Не учитывать все возможные переходы между состояниями

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

#Основные концепции

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

#1. Мемоизация (Top-down)

Рекурсивный подход с кэшированием результатов
Реализуется через декораторы или словари
В Python: @lru_cache декоратор

Пример:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

#2. Табуляция (Bottom-up)

Итеративный подход, заполнение таблицы от базовых случаев к целевому решению
Часто более эффективна по памяти и избегает проблем с глубиной рекурсии

Пример:

def fibonacci(n):
    if n <= 1:
        return n
    dp = [0, 1]
    for i in range(2, n+1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]

#Классические задачи DP

#Задача Фибоначчи

Базовый случай: F(0) = 0, F(1) = 1
Рекуррентное соотношение: F(n) = F(n-1) + F(n-2)
Сложность без DP: O(2ⁿ), с DP: O(n)

#Задача о рюкзаке (Knapsack)

Цель: максимизировать стоимость предметов при ограничении веса
Подзадачи: максимальная стоимость для первого i предметов и вместимости w
Сложность: O(n × W), где n — количество предметов, W — вместимость

#Наибольшая общая подпоследовательность (LCS)

Цель: найти длину наибольшей общей подпоследовательности двух строк
Подзадачи: LCS для префиксов строк
Сложность: O(m × n), где m, n — длины строк

#Практические рекомендации

Когда использовать DP
- Задача имеет оптимальную подструктуру (оптимальное решение состоит из оптимальных решений подзадач)
- Задача имеет перекрывающиеся подзадачи (одни и те же подзадачи решаются многократно)
Выбор подхода
- Мемоизация: проще в реализации, интуитивно понятна
- Табуляция: эффективнее по памяти, избегает stack overflow
Оптимизации
- Используйте только необходимые состояния (space optimization)
- Для больших значений рассмотрите матричное возведение в степень (для линейных рекуррентных соотношений)
- Учитывайте границы задачи для оптимизации размера таблицы
Типичные ошибки
- Забыть базовый случай в рекурсии
- Неправильное определение подзадач
- Не учитывать все возможные переходы между состояниями