Динамическое программирование: от рекурсии к оптимальности

🎯 Зачем это нужно?

Представь: ты разрабатываешь навигатор для Яндекс.Карт 🗺️. Нужно найти кратчайший путь от дома до школы через весь город. Наивный подход: проверить ВСЕ возможные пути. Но в городе миллионы маршрутов - компьютер зависнет навсегда!

Динамическое программирование решает такие задачи за секунды. Вот где оно работает прямо сейчас: - 📱 YouTube рекомендации - какие видео показать следующими - 🎮 Игровой ИИ - как AlphaGo победил чемпиона мира в го - 💰 Криптовалюты - оптимальная стратегия торговли - 🧬 Биоинформатика - поиск похожих участков ДНК

📚 История вопроса

В 1940-х математик Ричард Беллман работал над задачами военного планирования. Ему нужно было оптимизировать сложные многошаговые решения. Термин “динамическое программирование” он выбрал специально, чтобы министр обороны не понял, чем он занимается! 😄

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

💡 Интуиция

Основная идея: Не пересчитывай одно и то же дважды!

Допустим, ты идёшь в спортзал и хочешь набрать мышечную массу максимально эффективно 💪. У тебя есть разные упражнения с разной “стоимостью” (время) и “пользой” (результат).

Наивный подход: перебрать все возможные комбинации тренировок. Но многие подкомбинации повторяются! Например, “жим + приседания” встречается в тысячах вариантов.

DP говорит: “Один раз посчитай оптимальную программу для N упражнений и бюджета времени T. Сохрани результат. Когда понадобится - просто посмотри в таблицу!”

[МЕДИА: image_01] Описание: Схема сравнения наивной рекурсии и динамического программирования Промпт: “educational diagram comparing naive recursion tree with memoized dynamic programming, showing repeated subproblems being cached, modern infographic style, blue and green colors, arrows showing optimization”

📐 Формальное определение

Динамическое программирование применимо к задачам с двумя свойствами:

1️⃣ Оптимальная подструктура: оптимальное решение содержит оптимальные решения подзадач

2️⃣ Перекрывающиеся подзадачи: одни и те же подзадачи возникают многократно

Принцип оптимальности Беллмана: Если путь A→C→B оптимален, то путь A→C тоже оптимален.

Уравнение Беллмана: V(s) = max{R(s,a) + γV(s′)} для всех действий a

где: - V(s) - оптимальная ценность состояния s
- R(s,a) - награда за действие a в состоянии s - γ - коэффициент дисконтирования - s′ - следующее состояние

🔍 Примеры с разбором

Пример 1: Числа Фибоначчи

Задача: Найти F(50), где F(n) = F(n-1) + F(n-2)

Наивная рекурсия: ```python def fib_naive(n): if n <= 1: return n return fib_naive(n-1) + fib_naive(n-2) Сложность: O(2ⁿ) - экспоненциальная! F(50) считается часами. Мемоизация (top-down DP): code Python memo = {} def fib_memo(n): if n in memo: return memo[n] if n <= 1: result = n else: result = fib_memo(n-1) + fib_memo(n-2) memo[n] = result return result Табулирование (bottom-up DP): code Python def fib_dp(n): dp = [0] * (n+1) dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n] Сложность: O(n) - линейная! F(50) за миллисекунды. [МЕДИА: image_02] Описание: Визуализация дерева вызовов для наивной рекурсии vs мемоизированной версии Промпт: “side-by-side comparison of fibonacci recursion trees, left showing exponential naive approach with many repeated calls, right showing memoized version with cached results, educational programming visualization” Пример 2: Задача о рюкзаке Контекст: Ты собираешься в поход. Рюкзак вмещает 10 кг. Есть предметы с весом и ценностью. Что взять? Предметы: {(вес=2, польза=3), (вес=3, польза=4), (вес=4, польза=5), (вес=5, польза=6)} Рекурентное соотношение: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) “Для i-го предмета и веса w: либо не берём (предыдущий результат), либо берём (если помещается) и добавляем к оптимуму оставшегося места” code Python def knapsack(weights, values, W): n = len(weights) dp = [[0 for _ in range(W+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for w in range(1, W+1):
        if weights[i-1] <= w:
            dp[i][w] = max(dp[i-1][w], 
                          dp[i-1][w-weights[i-1]] + values[i-1])
        else:
            dp[i][w] = dp[i-1][w]

return dp[n][W]

Пример 3: Редакционное расстояние (Левенштейна) Задача: Превратить слово “кот” в “код” минимальным числом операций (замена, вставка, удаление). Это основа проверки орфографии в Google Docs! 📝 dp[i][j] = минимальное число операций для превращения первых i символов первого слова в первые j символов второго code Python def edit_distance(word1, word2): m, n = len(word1), len(word2) dp = [[0] * (n+1) for _ in range(m+1)]

# Инициализация базовых случаев
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j

for i in range(1, m+1):
    for j in range(1, n+1):
        if word1[i-1] == word2[j-1]:
            dp[i][j] = dp[i-1][j-1]  # Символы совпадают
        else:
            dp[i][j] = 1 + min(dp[i-1][j],    # Удаление
                              dp[i][j-1],     # Вставка
                              dp[i-1][j-1])   # Замена

return dp[m][n]

🎮 Практика Базовый уровень 🟢 Задание 1: Лестница из n ступенек. За раз можно подняться на 1 или 2 ступеньки. Сколько способов подняться на вершину? Задание 2: Есть монеты номиналами [1, 3, 4]. Найди минимальное количество монет для суммы 6. Задание 3: Максимальная сумма элементов массива, если нельзя брать два соседних элемента. Массив: [2, 1, 4, 9]. Задание 4: Сколько способов разложить число n в сумму 1, 3 и 4? Для n = 5. Продвинутый уровень 🟡 Задание 5: Самая длинная возрастающая подпоследовательность в массиве [10, 9, 2, 5, 3, 7, 101, 18]. Задание 6: Палиндромное разбиение: минимальное число разрезов строки “aab”, чтобы все части были палиндромами. Задание 7: Максимальная прибыль от покупки-продажи акций. Цены: [7,1,5,3,6,4]. Можно совершить максимум 2 операции. Задание 8: Подсчитать количество уникальных путей в сетке m×n из левого верхнего в правый нижний угол (можно идти только вправо или вниз). Челлендж 🔴 Задание 9: Задача о разрезании стержня: стержень длины n, массив цен для каждой длины. Найти максимальную выручку. Задание 10: Regex matching: строка s соответствует шаблону p с поддержкой ‘.’ (любой символ) и ‘*’ (ноль или более предыдущих символов). Задание 11: Burst Balloons: есть массив чисел (шарики). При “лопании” шарика i получаешь nums[i-1] × nums[i] × nums[i+1] очков. Найти максимальный счёт. ⚠️ Частые ошибки ❌ Ошибка: Пытаются применить DP везде, даже где он не нужен ✅ Правильно: Сначала проверить наличие оптимальной подструктуры и перекрывающихся подзадач 💡 Почему: DP эффективен только при повторных вычислениях одинаковых подзадач ❌ Ошибка: Неправильное определение состояния dp[i] ✅ Правильно: Состояние должно однозначно характеризовать подзадачу 💡 Почему: Плохо определённое состояние приводит к неверному результату ❌ Ошибка: Забывают инициализировать базовые случаи ✅ Правильно: Всегда явно определять dp[0], dp[1] и т.д. 💡 Почему: Базовые случаи - фундамент для построения решения ❌ Ошибка: Используют O(n²) памяти там, где достаточно O(n) ✅ Правильно: Анализировать зависимости и оптимизировать пространство 💡 Почему: Экономия памяти критична для больших задач ❌ Ошибка: Путают top-down (мемоизация) и bottom-up (табулирование) ✅ Правильно: Top-down идёт от ответа к базе, bottom-up - наоборот 💡 Почему: Разные подходы имеют разную сложность и применимость 🎓 Главное запомнить ✅ Принцип: Решаем каждую подзадачу только один раз и сохраняем результат ✅ Условия применимости: Оптимальная подструктура + перекрывающиеся подзадачи ✅ Два подхода: Мемоизация (сверху вниз) и табулирование (снизу вверх) ✅ Временная сложность: Обычно O(количество состояний × время перехода) 🔗 Связь с другими темами Откуда пришли: Рекурсия и математическая индукция (урок 269) заложили основы для понимания подзадач и их композиции. Куда ведёт: Жадные алгоритмы - альтернативный подход к оптимизации Теория игр - где каждый ход влияет на будущие возможности Машинное обучение - reinforcement learning использует уравнения Беллмана Алгоритмы на графах - кратчайшие пути, потоки Практическое применение: В олимпиадном программировании DP встречается в 30-40% задач. В промышленности - основа для рекомендательных систем, планирования ресурсов, финансового моделирования.