Кодик
Начать бесплатно

Динамическое программирование для чайников: от "что это вообще такое?" до решения задач с собеседований

Понятное объяснение динамического программирования с примерами на Python и JS. 5 классических задач, пошаговая методика решения.

АлгоритмыРазработка

6 мин

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

Представьте, что вы считаете факториал числа 5.

Для этого нужно: 5 × 4 × 3 × 2 × 1. А теперь вас просят посчитать факториал 6. Глупо заново всё пересчитывать, правда? Вы же уже знаете, что 5! = 120, просто умножьте на 6.

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

Главные признаки задач на ДП:

🎯 Оптимальная подструктура

Решение большой задачи состоит из решений маленьких подзадач

🔄 Перекрывающиеся подзадачи

Одни и те же подзадачи встречаются много раз

⚡ Нужно найти оптимум

Максимум, минимум или количество способов

Два подхода к ДП: мемоизация и табуляция

1. Мемоизация (сверху вниз)

Это рекурсия + кеширование результатов. Начинаем с большой задачи и спускаемся к базовым случаям.

def fibonacci_memo(n, memo={}):
    # Базовые случаи
    if n <= 1:
        return n
    
    # Проверяем кеш
    if n in memo:
        return memo[n]
    
    # Вычисляем и сохраняем
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

print(fibonacci_memo(50))  # Мгновенно!

Когда использовать: когда логика задачи интуитивно понятна через рекурсию.

2. Табуляция (снизу вверх)

Строим таблицу решений от базовых случаев к финальному ответу. Никакой рекурсии!

def fibonacci_table(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]

print(fibonacci_table(50))

Когда использовать: когда нужна максимальная производительность и контроль над памятью.

Классические задачи ДП, которые нужно знать в 2026

Задача 1: Числа Фибоначчи

Сложность без ДП: O(2ⁿ) — экспоненциальная!
Сложность с ДП: O(n) — линейная!

Мы уже видели решение выше. Это идеальная задача для старта.

Задача 2: Задача о рюкзаке (Knapsack Problem)

Вы грабитель с рюкзаком вместимостью W. Есть предметы с весом и ценностью. Как взять максимальную ценность?

def knapsack(weights, values, capacity):
    n = len(weights)
    # dp[i][w] = максимальная ценность при i предметах и вместимости w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            # Не берём предмет
            dp[i][w] = dp[i-1][w]
            
            # Берём предмет, если он влезает
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
    
    return dp[n][capacity]

weights = [1, 2, 3, 5]
values = [10, 5, 15, 7]
capacity = 7

print(knapsack(weights, values, capacity))  # 32

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

Задача 3: Longest Common Subsequence (LCS)

Найти самую длинную общую подпоследовательность двух строк. Основа для git diff!

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

print(lcs("ABCDGH", "AEDFHR"))  # 3 (ADH)

Применение: системы контроля версий, проверка на плагиат, биоинформатика (сравнение ДНК).

Задача 4: Coin Change (Размен монет)

Есть монеты разного номинала. Сколькими способами можно собрать сумму?

def coin_change(coins, amount):
    # dp[i] = минимальное количество монет для суммы i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Для суммы 0 нужно 0 монет
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

coins = [1, 2, 5]
amount = 11print(coin_change(coins, amount))  # 3 (5+5+1)

Применение: финтех-приложения, кассовые системы, оптимизация транзакций.

Задача 5: Edit Distance (Расстояние Левенштейна)

Минимальное количество операций для превращения одной строки в другую.

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]

print(edit_distance("kitten", "sitting"))  # 3

Применение: исправление опечаток, поисковые системы, автокомплит.

Пошаговая методика решения задач на ДП

Шаг 1: Найдите рекурсивное решение

Сначала просто решите задачу рекурсией, не думая об оптимизации.

# Неоптимизированная версияdef fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Шаг 2: Добавьте мемоизацию

Добавьте словарь для хранения результатов.

def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

Шаг 3: Преобразуйте в табуляцию (опционально)

Переведите на итеративный подход с массивом.

def fib_table(n):
    if n <= 1:
        return 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]

Шаг 4: Оптимизируйте память

Часто можно использовать O(1) памяти вместо O(n).

def fib_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    return prev1

Ключевые паттерны ДП в 2026

1D ДП

Одномерный массив

  • Числа Фибоначчи

  • Climbing Stairs

  • House Robber

2D ДП

Двумерный массив

  • Longest Common Subsequence

  • Edit Distance

  • Knapsack Problem

ДП на строках

Работа с текстом

  • Palindrome Subsequences

  • String Matching

  • Wildcard Matching

ДП на деревьях

Древовидные структуры

  • Binary Tree Maximum Path Sum

  • Diameter of Binary Tree

ДП на графах

Графовые алгоритмы

  • Shortest Path (Bellman-Ford)

  • Traveling Salesman Problem

Типичные ошибки начинающих

Ошибка 1: Забывают базовые случаи

def fib(n):
    return fib(n-1) + fib(n-2)
# Бесконечная рекурсия!

Правильно

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Ошибка 2: Неправильный размер таблицы

dp = [0] * n
# Если нужны индексы 0..n,
# нужен размер n+1!

Правильно

dp = [0] * (n + 1)

Ошибка 3: Не проверяют границы

if dp[i-1]:
# Что если i = 0?

Правильно

if i > 0 and dp[i-1]:

Практические советы для собеседований.

  1. Рисуйте таблицу на бумаге — визуализация помогает найти зависимости

  2. Начинайте с малых примеров — fib(0), fib(1), fib(2)...

  3. Ищите формулу рекуррентности — как dp[i] зависит от предыдущих значений?

  4. Проговаривайте логику вслух — это показывает ход ваших мыслей

  5. Не бойтесь сначала написать неоптимальное решение — потом его можно улучшить

JavaScript-версия для веб-разработчиков.

Многие начинающие работают с JavaScript, поэтому вот пример на JS:

// Мемоизацияfunction fibMemo(n, memo = {}) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];
    
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

// Табуляцияfunction fibTable(n) {
    if (n <= 1) return n;
    
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

// Оптимизированная версия (O(1) памяти)function fibOptimized(n) {
    if (n <= 1) return n;
    
    let prev2 = 0, prev1 = 1;
    
    for (let i = 2; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

console.log(fibOptimized(50)); // 12586269025

Заключение.

Динамическое программирование — это не магия, а логичный подход к решению задач. Ключевые моменты:

  1. Разбивайте на подзадачи — найдите паттерн повторения

  2. Сохраняйте результаты — не считайте дважды

  3. Начинайте с рекурсии — потом оптимизируйте

  4. Тренируйтесь регулярно — ДП требует практики

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

✅ Пройдёте большинство технических собеседований

✅ Сможете оптимизировать реальные задачи в продакшене

✅ Поймёте, как работают внутренности многих библиотек и фреймворков

✅ Научитесь мыслить алгоритмически

Помните: каждый алгоритм когда-то казался сложным даже лучшим разработчикам. Главное — практика и терпение.

Изучить динамическое программирование и многие другие важные темы можно в Кодике — образовательной платформе с практическими курсами для разработчиков. Мы создаём контент, который реально помогает на собеседованиях и в работе!

📱 А ещё у нас есть крутой Telegram-канал с дружеским комьюнити, где:

  • Разбираем задачи с собеседований

  • Делимся полезными статьями

  • Помогаем друг другу расти

  • Обсуждаем последние тренды в разработке

Перейти в Кодик Присоединиться к Telegram

Присоединяйся к комьюнити разработчиков, которые растут вместе! 💪

Комментарии