---
title: "Динамическое программирование (1-D)"
url: https://algopath.pro/ru/patterns/dynamic-programming
language: ru
summary: "Ответьте на маленькую версию задачи, сохраните ответ и стройте из него следующий. Каждое состояние считается только один раз."
updated: 2026-08-24
---

# Динамическое программирование (1-D)

Ответьте на маленькую версию задачи, сохраните ответ и стройте из него следующий. Каждое состояние считается только один раз.

## Динамическое программирование (1-D): как это работает?

Решите, что означает одно состояние. Обычно это лучший ответ по первым i элементам.

Запишите переход: как состояние i следует из более ранних. Этот переход и есть весь алгоритм.

Базовые случаи заполните вручную. Это состояния, под которыми нет ничего меньшего.

Идите вперёд и заполняйте таблицу по порядку. Всё, что она читает, уже посчитано.

Ответ лежит в одной ячейке, обычно в последней. Иногда это наибольшая ячейка таблицы.

Если переход смотрит только на два состояния назад, хватит двух переменных. Массив тогда не нужен.

- `dp[0] = 2` Грабим дома [2, 7, 9]. Только первый даёт 2.
- `dp[1] = 7` Берём лучшее из 2 и 7. Соседние дома вместе брать нельзя.
- `dp[2] = max(7, 2 + 9)` Либо пропустить третий дом, либо взять его вместе с dp[0].
- `dp[2] = 11` Выигрывает вариант с первым и третьим домом.
- `ответ = 11` Три состояния, каждое посчитано ровно один раз.

## Динамическое программирование (1-D): когда применять?

- лучшее/максимум/минимум, заканчивающееся в позиции i
- число способов дойти, подняться или замостить
- нельзя брать два соседних элемента
- минимальная стоимость пути по сетке
- повторяющиеся подзадачи, одно и то же состояние считается заново

## Динамическое программирование (1-D): с чем путают?

- **Рекурсия с мемоизацией** - Мемоизация заполняет ту же таблицу сверху и по требованию. Здесь она заполняется снизу в заданном порядке.
- **Жадный алгоритм (обменный аргумент)** - Жадность выбирает один вариант на шаг. Динамика держит все варианты до конца.
- **Рекурсия** - Рекурсия показывает, каким будет переход. Скорость даёт именно таблица.
- **DP над подпоследовательностями (LIS / LCS / расстояние редактирования)** - Там состояние это пара позиций в двух последовательностях. Здесь хватает одного индекса.

## Динамическое программирование (1-D): сложность по времени и памяти

n состояний по O(1) работы дают O(n). Память падает до O(1), когда важны только последние состояния.

## Динамическое программирование (1-D): разбор примера

### Наибольшая сумма непрерывного отрезка

Верните наибольшую сумму любого непрерывного отрезка массива.

Значения бывают отрицательными, поэтому ответ это не просто общая сумма.

Пусть состояние i это лучшая сумма отрезка, кончающегося на индексе i.

Либо прошлый отрезок продолжается, либо здесь начинается новый. Ответ это наибольшее состояние.

```javascript
function maxSubArray(nums) {
    let best = nums[0];
    let endingHere = nums[0]; // only the previous state matters, so no array

    for (let i = 1; i < nums.length; i++) {
        // continue the stretch, or start a new one right here
        endingHere = Math.max(nums[i], endingHere + nums[i]);
        best = Math.max(best, endingHere);
    }

    return best;
}
```

## Динамическое программирование (1-D): частые ошибки

- **Состояние не определяет будущее** Если две ситуации с одним состоянием ведут себя по-разному, состояние неполное. Добавьте недостающее.
- **Заполняют таблицу в неверном порядке** Ячейку надо записать до того, как её прочитают. Идите в направлении, которого требует переход.
- **Читают ответом не ту ячейку** Для состояния лучший-кончающийся-здесь ответом служит максимум. Это не последняя ячейка.
- **Забывают базовые случаи** Пустой вход или вход из одного элемента ломают большинство решений. Разберите их первыми.

## Динамическое программирование (1-D): задачи с собеседований

- **Подъём по лестнице** Каждая ступень приходит с одной или двух назад.
- **Ограбление домов** Взять этот дом вместе с домом через один или пропустить.
- **Максимальный подмассив** Продолжить отрезок или начать новый.
- **Размен монет** Состояние это сумма, а каждая монета это ветка.
- **Число способов расшифровки** Одна цифра или две, если пара допустима.
- **Минимальная стоимость подъёма** Та же форма, но со стоимостью каждой ступени.
- **Числа Фибоначчи** Самый короткий переход из всех возможных.

## JavaScript

```javascript
function maxSubarraySum(nums) {
    let best = nums[0];
    let curr = nums[0];
    for (let i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);
        best = Math.max(best, curr);
    }
    return best;
}
```

## Python

```python
def max_subarray_sum(nums):
    best = curr = nums[0]
    for x in nums[1:]:
        curr = max(x, curr + x)
        best = max(best, curr)
    return best
```

## PHP

```php
function maxSubarraySum(array $nums): int {
    $best = $curr = $nums[0];
    for ($i = 1; $i < count($nums); $i++) {
        $curr = max($nums[$i], $curr + $nums[$i]);
        $best = max($best, $curr);
    }
    return $best;
}
```