---
title: "DP на строках (word break)"
url: https://algopath.pro/ru/patterns/dp-strings
language: ru
summary: "Режьте строку в каждой позиции и спрашивайте, годится ли получившийся кусок. Таблица достижимых позиций убирает повторы."
updated: 2026-08-24
---

# DP на строках (word break)

Режьте строку в каждой позиции и спрашивайте, годится ли получившийся кусок. Таблица достижимых позиций убирает повторы.

## DP на строках (word break): как это работает?

Состояние i значит, что первые i символов можно разрезать. Нулевое состояние истинно по определению.

Для каждой позиции i смотрите назад на все более ранние позиции j. Кусок между ними это кандидат в слово.

Разрез работает, если состояние j истинно и кусок это слово. Тогда истинно и состояние i.

Одного подходящего j достаточно. Прерывайте внутренний цикл сразу после находки.

Ответ лежит в последнем состоянии. Дальше позиции n ничего нет.

Каждая позиция решается ровно один раз. Именно это превращает экспоненту в таблицу.

- `dp[0] = истина` Режем leetcode словами leet и code.
- `dp[1] по dp[3] = ложь` Куски l, le и lee словами не являются.
- `dp[4] = истина` leet это слово, а dp[0] истинно.
- `dp[5] по dp[7] = ложь` Ни одно слово не кончается в этих позициях.
- `dp[8] = истина` code идёт после dp[4]. Вся строка режется.

## DP на строках (word break): когда применять?

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

## DP на строках (word break): с чем путают?

- **DP над подпоследовательностями (LIS / LCS / расстояние редактирования)** - Там выравниваются две разные последовательности. Здесь режется одна строка.
- **Trie (префиксное дерево)** - Trie ускоряет поиск по словарю. Логика разрезания над ним не меняется.
- **Бэктрекинг** - Бэктрекинг перечисляет все верные разрезы. Таблица отвечает лишь, есть ли хоть один.
- **Хеш-множество / словарь** - Словарь слов обычно и есть множество. Таблица нужна, чтобы не проверять суффикс заново.

## DP на строках (word break): сложность по времени и памяти

n символов при словах до m дают O(nm). Множество или trie держат поиск около O(1).

## DP на строках (word break): разбор примера

### Наименьшее число разрезов на палиндромы

Разрежьте строку на куски, каждый из которых палиндром. Верните наименьшее число разрезов.

Один символ уже считается палиндромом.

Сначала отметьте все пары позиций, между которыми стоит палиндром.

Потом состояние i это наименьшее число разрезов для первых i символов. Палиндромный хвост стоит одного разреза.

```javascript
function minCut(s) {
    const n = s.length;
    const isPal = Array.from({ length: n }, () => new Array(n).fill(false));

    for (let end = 0; end < n; end++) {
        for (let start = end; start >= 0; start--) {
            // the inside is already decided, because end - start only shrinks
            if (s[start] === s[end] && (end - start < 2 || isPal[start + 1][end - 1])) {
                isPal[start][end] = true;
            }
        }
    }

    const cuts = new Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) cuts[i] = i - 1; // cuts[0] is -1, so a whole palindrome costs 0

    for (let end = 0; end < n; end++) {
        for (let start = 0; start <= end; start++) {
            if (isPal[start][end]) {
                cuts[end + 1] = Math.min(cuts[end + 1], cuts[start] + 1);
            }
        }
    }

    return cuts[n];
}
```

## DP на строках (word break): частые ошибки

- **Пересобирают подстроку на каждом шаге** Вырезание внутри цикла каждый раз копирует символы. Сравнивайте позиции или идите по trie.
- **Идут по палиндромам не в ту сторону** Внутренность обязана решаться раньше внешней. Растите по длине или ведите начало назад.
- **Забывают пустой префикс** Нулевое состояние и позволяет первому слову начать разрез. Без него истины не будет никогда.
- **Перечисляют все разрезы, когда хватит одного** Задача спрашивает только да или нет. Перечисление разрезов экспоненциально.

## DP на строках (word break): задачи с собеседований

- **Разбиение строки на слова** Можно ли вообще разрезать строку.
- **Разбиение строки на слова II** Нужны все верные разрезы, поэтому возвращается бэктрекинг.
- **Разбиение на палиндромы II** Нужно число разрезов, а не сами части.
- **Наибольшая палиндромная подстрока** Та же таблица палиндромов, прочитанная иначе.
- **Составные слова** Каждое слово режется при помощи всех остальных.
- **Лишние символы в строке** Считается стоимость оставшихся букв.
- **Число способов расшифровки** Одна цифра или две, по фиксированному алфавиту.

## JavaScript

```javascript
function wordBreak(s, wordDict) {
    const words = new Set(wordDict);
    const ok = new Array(s.length + 1).fill(false);
    ok[0] = true;
    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j < i; j++) {
            if (ok[j] && words.has(s.slice(j, i))) {
                ok[i] = true;
                break;
            }
        }
    }
    return ok[s.length];
}
```

## Python

```python
def word_break(s, word_dict):
    words = set(word_dict)
    ok = [False] * (len(s) + 1)
    ok[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if ok[j] and s[j:i] in words:
                ok[i] = True
                break
    return ok[len(s)]
```

## PHP

```php
function wordBreak(string $s, array $wordDict): bool {
    $words = array_flip($wordDict);
    $n = strlen($s);
    $ok = array_fill(0, $n + 1, false);
    $ok[0] = true;
    for ($i = 1; $i <= $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($ok[$j] && isset($words[substr($s, $j, $i - $j)])) {
                $ok[$i] = true;
                break;
            }
        }
    }
    return $ok[$n];
}
```