---
title: "DP на интервалах"
url: https://algopath.pro/ru/patterns/dp-interval
language: ru
summary: "Состояние здесь это отрезок, а переход выбирает последний ход внутри него. Короткие отрезки всегда заполняются раньше длинных."
updated: 2026-08-24
---

# DP на интервалах

Состояние здесь это отрезок, а переход выбирает последний ход внутри него. Короткие отрезки всегда заполняются раньше длинных.

## DP на интервалах: как это работает?

Состояние это пара, два конца отрезка. Оно хранит лучший результат внутри этих границ.

Идите по длине отрезка, от коротких к длинным. Всё, что вы читаете, уже посчитано.

Для одного отрезка переберите все точки разреза внутри. Каждый разрез даёт одного кандидата.

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

Вся задача сидит именно в стоимости соединения. В шариках она зависит от двух границ.

Ответ это состояние, накрывающее весь вход. Оно заполняется самым последним.

- `с полями: [1, 3, 1, 5, 1]` Лопаем шарики. По краям добавлена единица, она не лопается.
- `отрезки ширины один: 0` Внутри них лопать нечего.
- `dp(1, 3) = 15` Единица между 3 и 5 даёт 3 умножить на 1 и на 5.
- `dp(0, 3) = 30` Тройку лопаем последней, поэтому она стоит 1 на 3 на 5.
- `dp(0, 4) = 35` Пятёрка идёт последней. Все короткие отрезки уже готовы.

## DP на интервалах: когда применять?

- объединить соседние части с некоторой стоимостью
- лучший способ разбить отрезок на две части
- порядок перемножения цепочки матриц
- стоимость слияния зависит от всего отрезка
- оптимальная расстановка скобок или порядок построения

## DP на интервалах: с чем путают?

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

## DP на интервалах: сложность по времени и памяти

n примерно до 500 даёт O(n в кубе). Отрезков n в квадрате, и у каждого n точек разреза.

## DP на интервалах: разбор примера

### Наибольшая палиндромная подпоследовательность

Верните длину наибольшей палиндромной подпоследовательности строки.

Буквы не обязаны стоять рядом друг с другом.

Состоянием служит отрезок строки.

Если концы совпали, они добавляют двойку к внутреннему отрезку. Иначе отбросьте один конец и возьмите лучшее.

```javascript
function longestPalindromeSubseq(s) {
    const n = s.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));

    // i walks backwards so every inner range is already filled
    for (let i = n - 1; i >= 0; i--) {
        dp[i][i] = 1; // a single letter is a palindrome

        for (let j = i + 1; j < n; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[0][n - 1];
}
```

## DP на интервалах: частые ошибки

- **Гоняют i и j как в обычной сетке** Отрезок заполняется после всего, что внутри него. Идите по длине или ведите i назад.
- **Выбирают первый ход вместо последнего** В шариках фиксированных соседей имеет только последний лопнувший. Выбор первого делает состояние неверным.
- **Забывают про поля по краям** Нейтральное значение с каждой стороны убирает крайние случаи. Без него границы требуют отдельного кода.
- **Запускают это на большом входе** O(n в кубе) умирает после нескольких тысяч элементов. Проверьте n до написания трёх циклов.

## DP на интервалах: задачи с собеседований

- **Лопающиеся шарики** Выбирается шарик, который лопнет последним.
- **Наибольшая палиндромная подпоследовательность** Концы совпали или один из них отброшен.
- **Минимальная триангуляция многоугольника** Каждая точка разреза даёт треугольник.
- **Странный принтер** Одна печать накрывает целый отрезок.
- **Удаление коробок** Состояние несёт ещё и счётчик рядом с отрезком.
- **Число палиндромных подстрок** Считается каждый отрезок, который является палиндромом.
- **Минимальная стоимость слияния камней** Деление идёт на группы по k, а не надвое.

## JavaScript

```javascript
function minMergeCost(sizes) {
    const n = sizes.length;
    const prefix = [0];
    for (const s of sizes) prefix.push(prefix[prefix.length - 1] + s);
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i + len - 1 < n; i++) {
            const j = i + len - 1;
            dp[i][j] = Infinity;
            for (let k = i; k < j; k++) {
                const cost = dp[i][k] + dp[k + 1][j] + (prefix[j + 1] - prefix[i]);
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n - 1];
}
```

## Python

```python
def min_merge_cost(sizes):
    n = len(sizes)
    prefix = [0]
    for s in sizes:
        prefix.append(prefix[-1] + s)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = min(
                dp[i][k] + dp[k + 1][j] + (prefix[j + 1] - prefix[i])
                for k in range(i, j)
            )
    return dp[0][n - 1]
```

## PHP

```php
function minMergeCost(array $sizes): int {
    $n = count($sizes);
    $prefix = [0];
    foreach ($sizes as $s) $prefix[] = end($prefix) + $s;
    $dp = array_fill(0, $n, array_fill(0, $n, 0));
    for ($len = 2; $len <= $n; $len++) {
        for ($i = 0; $i + $len - 1 < $n; $i++) {
            $j = $i + $len - 1;
            $dp[$i][$j] = PHP_INT_MAX;
            for ($k = $i; $k < $j; $k++) {
                $cost = $dp[$i][$k] + $dp[$k + 1][$j] + ($prefix[$j + 1] - $prefix[$i]);
                $dp[$i][$j] = min($dp[$i][$j], $cost);
            }
        }
    }
    return $dp[0][$n - 1];
}
```