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

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

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

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

Контент

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

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

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

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

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

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

**Динамічне програмування (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 (табуляція): будуємо таблицю від баз до відповіді. Контролюємо порядок і пам'ять, немає глибокої рекурсії.

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

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

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

#### Фібоначчі - мемоізація (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, коли що обирати.
- Наведіть міні-приклад (Фібоначчі/рюкзак) зі станом, переходом та оцінкою складності.
- Згадайте оптимізацію пам'яті та відновлення відповіді.

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

Для рев’юера

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

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