Що таке динамічне програмування (DP)?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Динамічне програмування (DP) - це метод розв'язання задач шляхом розбиття їх на перекривні підзадачі, запам'ятовування результатів (мемоізація) або послідовного нарощування таблиці відповідей (табуляція), використовуючи властивість оптимальної підструктури.

Ознаки: оптимальна підструктура та перекривні підзадачі.
Підходи: Top-Down (мемоізація) та Bottom-Up (табуляція).
Мета: знизити експоненційну складність до поліноміальної.

Детальний розбір

DP застосовують, коли найкраще рішення задачі можна зібрати з найкращих рішень її підзадач, а самі підзадачі повторюються. Замість повторних обчислень ми зберігаємо результати і повторно їх використовуємо.

Коли застосовувати DP

Є оптимальна підструктура: оптимум великої задачі будується з оптимумів менших.
Підзадачі перекриваються: множина повторюваних обчислень.
Приклади: Фібоначчі, рюкзак 0/1, шляхи в сітці, розмін монет, LCS/LIS, редагування рядків (Левенштейн).

Ключові ідеї

Стан (state): як параметризувати підзадачу, наприклад dp[i][w] - найкраща відповідь для перших i предметів і ваги w.
Перехід (recurrence): як обчислити поточний стан через менші.
База: значення для найменших випадків.
Порядок обчислень: топологічний порядок залежностей.

Підходи: Top-Down та Bottom-Up

Top-Down (мемоізація): рекурсивно розв'язуємо підзадачу і кешуємо результат. Простіше писати, повторює математичне визначення, але є ризик переповнення стека.
Bottom-Up (табуляція): будуємо таблицю від баз до відповіді. Контролюємо порядок і пам'ять, немає глибокої рекурсії.

Шаблон розв'язання

Визначте стан dp (які параметри достатньо зберігати).
Опишіть базові випадки (ініціалізація).
Виведіть перехід (recurrence).
Оберіть порядок обчислення (або використовуйте рекурсію + мемоізацію).
Визначте, де міститься відповідь (dp[n], dp[n][m], максимум по рядку/стовпцю тощо).
Оцініть складність за часом і пам'яттю.
За потреби заплануйте зберігання вказівників/відновлення розв'язку зворотним проходом.

Приклади коду

Фібоначчі - мемоізація (Top-Down)

python

from functools import lru_cache

@lru_cache(None)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))  # 55

Фібоначчі - табуляція (Bottom-Up)

python

def fib(n: int) -> int:
    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]

print(fib(10))  # 55

Рюкзак 0/1 (максимальна цінність за обмеження ваги)

Стан: dp[i][w] - максимальна цінність, використовуючи перші i предметів при допустимій вазі w.

Перехід: dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i-1]] + val[i-1]) якщо wt[i-1] <= w, інакше dp[i][w] = dp[i-1][w].

python

from typing import List

def knapsack(W: int, wt: List[int], val: List[int]) -> int:
    n = len(wt)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if wt[i - 1] <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1])
    return dp[n][W]

print(knapsack(7, [1, 3, 4, 5], [1, 4, 5, 7]))  # 9

Підрахунок шляхів у сітці (оптимізація пам'яті)

Кількість шляхів з (0,0) до (m-1,n-1) при рухах праворуч/вниз. Стан: dp[j] - кількість шляхів до поточної клітинки в рядку. Перехід: dp[j] += dp[j-1].

python

def unique_paths(m: int, n: int) -> int:
    dp = [1] * n  # базовий перший рядок: тільки праворуч
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    return dp[-1]

print(unique_paths(3, 7))  # 28

Оптимізація пам'яті та відновлення відповіді

Оптимізація пам'яті: зводьте dp до 1D або двох ковзних рядків/стовпців, якщо перехід використовує лише сусідні шари.
Відновлення розв'язку: зберігайте вказівники (parent/choice) або перераховуйте, рухаючись від відповіді назад за перевіркою рівностей переходу.

Типові помилки в DP

Неправильно визначений стан (бракує параметрів або їх забагато).
Неповні базові випадки: некоректна ініціалізація меж.
Неправильний порядок обчислень для табуляції.
Переповнення стека при глибокій рекурсії (краще перейти на Bottom-Up).

Як відповідати на співбесіді

Дайте визначення DP і дві ознаки: оптимальна підструктура, перекривні підзадачі.
Опишіть Top-Down та Bottom-Up, коли що обирати.
Наведіть міні-приклад (Фібоначчі/рюкзак) зі станом, переходом та оцінкою складності.
Згадайте оптимізацію пам'яті та відновлення відповіді.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.