Что такое динамическое программирование (мемоизация против табуляции)?

Question

Accepted Answer

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

## Идея

Наивная рекурсия перевычисляет одни и те же подзадачи экспоненциально много раз. DP кэширует их, сокращая экспоненциальную сложность до полиномиальной.

## Мемоизация (нисходящий подход)

```python
from functools import lru_cache

@lru_cache(maxsize=None)               # cache results automatically
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)     # each n computed once
```

## Табуляция (восходящий подход)

```python
def fib_table(n):
    if n < 2:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])  # build up from base cases
    return dp[n]
```

## Мемоизация против табуляции

| | Мемоизация | Табуляция |
|---|------------|------------||
| Направление | рекурсия сверху вниз | итерация снизу вверх |
| Вычисляет | только нужные состояния | все состояния |
| Риск | переполнение стека | нет |
| Память | может быть оптимизирована | часто приводится к O(1) строкам |

## Сложность

Числа Фибоначчи: от O(2ⁿ) наивного подхода к **O(n)** по времени, O(n) (или O(1)) по памяти.

## Когда использовать / подводные камни

Используйте DP когда подзадачи **перекрываются**. Тщательно определите состояние и рекуррентное соотношение — это самая сложная часть. Если подзадачи не перекрываются, обычного разделяй и властвуй достаточно.

## Почему это важно

DP преобразует неразрешимые экспоненциальные задачи — поиск кратчайшего пути, расстояние редактирования, задача о рюкзаке — в эффективные решения.

Навык определения состояния и рекуррентного соотношения является одним из наиболее ценных на собеседованиях по алгоритмам.

Он лежит в основе реальных систем от инструментов diff до выравнивания последовательностей в биоинформатике.