Що означає "перетин підзадач" у динамічному програмуванні?

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

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

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

Детальна відповідь

Визначення та інтуїція

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

Є підпроблеми, які повторюються в різних гілках обчислень.
Кількість унікальних станів обмежена (зазвичай параметрами підзадачі: індекси, залишок, сума тощо).
Разом із перетином зазвичай потрібна оптимальна підструктура - оптимальна відповідь задачі будується з оптимальних відповідей підзадач.

Класичний приклад: числа Фібоначчі

Наївна рекурсія багаторазово переобчислює одні й ті самі F(k) - яскравий перетин підзадач.

python

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

# Виклики F(3), F(2) та інші повторюються багаторазово -> експоненційна складність O(phi^n).

DP усуває повтори: мемоізація (top-down) або табуляція (bottom-up).

python

# Мемоізація (top-down)
from functools import lru_cache

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

# Складність: O(n) за часом і O(n) за пам'яттю (кеш/стек).

python

# Табуляція (bottom-up)
def fib_tab(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

# Складність: O(n) часу, O(1) пам'яті.

Ще приклади задач із перетином підзадач

Кількість шляхів у сітці: стан (i, j) зустрічається під час підрахунку шляхів із (i-1, j) та (i, j-1). DP: dp[i][j] = dp[i-1][j] + dp[i][j-1].
LCS (найдовша спільна підпослідовність): стан (i, j) для префіксів рядків повторюється в різних гілках порівняння символів.
Розмін монет/сума підмножиною: стани (remaining_sum, idx) зустрічаються з різних шляхів вибору/пропуску монети.

Як розпізнати, що є перетин підзадач

Побудуйте рекурсивну формулу і подумки розгорніть кілька рівнів дерева викликів: бачите однакові стани? Це воно.
Параметрів у підзадачі мало, а їхні діапазони обмежені (наприклад, індекси i, j, залишок r) -> кількість унікальних станів скінченна і невелика.
Наївна рекурсія дає експоненційну складність, але є підозра, що можна повторно використати відповіді.

Порівняння з «розділяй і володарюй»

Розділяй і володарюй (quicksort/mergesort): підзадачі незалежні і не перетинаються - немає сенсу кешувати.
ДП: підзадачі повторюються -> кешування/таблиця критично важливі.

Типові помилки на співбесідах

Плутають перетин підзадач з оптимальною підструктурою: це різні властивості, але зазвичай потрібні обидві.
Пишуть рекурсію без кешу, втрачаючи виграш у часі.
Зберігають надто великий кеш, хоча частина станів недосяжна: можна оптимізувати пам'ять.

Практичний міні-приклад: кількість шляхів у сітці

Проблема: скільки шляхів з (0,0) до (m,n), рухаючись лише праворуч і вниз? Підзадачі dp[i][j] перекриваються, бо dp[i][j] використовується під час обчислення dp[i+1][j] та dp[i][j+1].

python

def grid_paths(m, n):
    dp = [[0]*(n+1) for _ in range(m+1)]
    dp[0][0] = 1
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 and j == 0:
                continue
            from_up = dp[i-1][j] if i > 0 else 0
            from_left = dp[i][j-1] if j > 0 else 0
            dp[i][j] = from_up + from_left
    return dp[m][n]

# Час O(m*n), пам'ять O(m*n) (можна скоротити до O(n) одним масивом).

Короткий конспект для відповіді на співбесіді

Перетин підзадач: одні й ті самі підпроблеми виникають багато разів.
Рішення: DP з мемоізацією (top-down) або табуляцією (bottom-up), щоб обчислювати кожну унікальну підзадачу один раз.
Перевірка: обмежена кількість станів + спостережувані повтори в дереві рекурсії.
Підсумок: зниження асимптотики (часто з експоненційної до поліноміальної).

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

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

Premium

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