Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що означає "перетин підзадач" у динамічному програмуванні?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

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

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

Перетин підзадач - це ситуація, коли множина унікальних підпроблем суттєво менша за загальну кількість їх викликів у наївному рекурсивному розгортанні. Іншими словами, одні й ті самі стани обчислюються знову і знову. 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), щоб обчислювати кожну унікальну підзадачу один раз.
- Перевірка: обмежена кількість станів + спостережувані повтори в дереві рекурсії.
- Підсумок: зниження асимптотики (часто з експоненційної до поліноміальної).

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати601 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.