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% задач. В промышленности - основа для рекомендательных систем, планирования ресурсов, финансового моделирования.