Подготовка к алгоритмической секции Яндекса: ключевые алгоритмы и структуры данных

Формат секции, оценка сложности и техника решения задач

Алгоритмическая секция в Яндексе (и похожих интервью/контестах) проверяет не знание редких трюков, а умение быстро:

понять задачу и ограничения

выбрать подходящий алгоритм и структуру данных

оценить сложность и уложиться во время

написать корректное решение без лишних багов

Эта статья задаёт базовую «операционную систему» для всего курса: как выглядит формат, как проверять сложность, и каким ритуалом решать задачи.

Как обычно устроена алгоритмическая секция

Точные детали зависят от конкретной команды и уровня, но чаще всего формат близок к соревновательному программированию.

Что вам дают

Несколько задач (обычно от 1 до 4), отсортированных по возрастанию сложности.

Ограничение по времени на каждую задачу или на весь набор.

Ограничение по памяти.

Входные данные (числа, строки, массивы, графы) и ожидаемый вывод.

Автоматическую проверку на большом наборе тестов.

Что от вас ожидают

Рабочее решение, проходящее все тесты.

Адекватную оценку сложности по времени и памяти.

Аккуратную реализацию (корректные типы, границы, быстрый ввод/вывод, без «магии»).

Типичные темы задач

Массивы и строки: префиксные суммы, два указателя, частоты.

Поиск: двоичный поиск по ответу, хеш-таблицы.

Сортировка и жадные стратегии.

Деревья/графы: BFS/DFS, кратчайшие пути в простых вариантах.

Динамическое программирование базового уровня.

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

!Конвейер решения задачи от чтения до отправки

Оценка сложности: что нужно уметь на автомате

Что такое сложность по времени

Сложность по времени обычно описывают через О-большое (Big-O): насколько растёт число операций при росте размера входа .

Примеры:

: один проход по массиву.

: сортировка массива.

: два вложенных цикла по .

Здесь:

— размер входа (например, длина массива).

— логарифм (на практике важен как «очень медленно растущая величина», основание не критично для Big-O).

Важно: Big-O описывает порядок роста, а не точное число наносекунд. Но на секции этого достаточно, чтобы понять: «пройдёт или нет».

Быстрая прикидка «пройдёт ли по времени»

В интервью и контестах полезна грубая инженерная оценка:

Для быстрых языков (например, C++) часто берут ориентир порядка простых операций за секунду.

Для более медленных интерпретируемых (например, Python) — порядка простых операций за секунду.

Это не закон физики, а практическая эвристика: реальные числа зависят от ввода/вывода, типов данных, констант и окружения.

Таблица-ориентир по ограничениям

| Типичный максимум | Что обычно проходит | Что обычно не проходит | |---:|---|---| | | | | | | , | | | | (иногда) | с большими константами, |

Как пользоваться таблицей:

Берёте максимальный размер входа из условия.

Смотрите, какие порядки сложности обычно укладываются.

Если ваш алгоритм «на грани», ищете оптимизацию или другой подход.

Как быстро оценивать сложность по коду

1) Последовательные куски кода складываются по времени, но порядок определяет самый «тяжёлый» кусок.

Например, + всё равно даёт .

2) Вложенные циклы обычно перемножаются.

Цикл по внутри цикла по даёт .

3) Частые «встроенные» операции:

Сортировка массива длины : обычно .

Двоичный поиск: .

Хеш-таблица (map/set в среднем): часто рассматривают как на операцию, значит на вставок/поисков.

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

Сложность по памяти

Память часто становится ограничением, когда вы храните большие массивы/матрицы.

Практическая оценка:

Массив на целых чисел — это памяти.

Матрица — это памяти и обычно «убивает» решение уже при (это невозможно) и становится проблемой даже при .

Вывод: если видите порядка , почти наверняка нельзя хранить матрицу смежности для графа и нельзя делать DP-таблицу размером .

!Наглядное сравнение роста типичных сложностей

Техника решения задач: пошаговый протокол

Ниже — рабочий протокол, который уменьшает число ошибок и ускоряет выход на правильное решение.

Понять задачу и переформулировать

Сделайте короткую переформулировку своими словами:

что дано

что нужно найти

какие гарантии (например, «массив отсортирован», «числа неотрицательные»)

Если решаете в паре с интервьюером, полезно проговорить эту версию вслух: так вы рано ловите неправильное понимание.

Выписать ограничения и крайние случаи

Ограничения отвечают на главный вопрос: какой класс алгоритмов вообще возможен.

Минимальный чек-лист:

максимальные размеры входа (например, , )

диапазоны значений (важно для переполнений и выбора типов)

есть ли отрицательные числа

возможны ли пустые структуры (например, )

что делать при нескольких ответах (любой или определённый)

Сначала придумать базовое решение (bruteforce)

Даже если оно медленное, оно выполняет две функции:

помогает убедиться, что вы понимаете задачу

становится «опорной точкой» для оптимизации

После этого вы сравниваете его сложность с ограничениями.

Проверить сложность и найти узкое место

Спросите себя:

где самый большой цикл/перебор

можно ли убрать вложенность

можно ли заменить перебор поиском/хешированием/двумя указателями

можно ли предобработать данные (префиксные суммы, частоты)

Типовые «замены» (подробно будут в следующих статьях):

перебор пар -> хеш-таблица для «дополнения до суммы» -> .

Поиск ответа среди чисел -> сортировка + два указателя -> .

«Найти минимальный X, при котором условие истинно» -> двоичный поиск по ответу -> проверок.

Зафиксировать инварианты и доказать корректность словами

Инвариант — это утверждение, которое остаётся истинным на каждом шаге алгоритма.

Примеры инвариантов:

В алгоритме двумя указателями: «окно всегда содержит текущий рассматриваемый отрезок и удовлетворяет условию».

В BFS: «первый раз попали в вершину — нашли кратчайшее расстояние по числу рёбер».

Короткое словесное доказательство почти всегда выявляет скрытые баги раньше кода.

Реализация: упрощайте, а не усложняйте

Практические правила:

Делайте код прямолинейным: меньше состояний — меньше ошибок.

Выносите повторяющееся в функции (но без фанатизма, чтобы не терять время).

Аккуратно с индексами (0/1), границами циклов, пустыми случаями.

Если нужно хранить «не найдено», используйте явные значения (например, -1) и проверяйте их.

Тестирование перед отправкой

Минимальный набор тестов, которые стоит прогнать в голове или локально:

самый маленький вход

самый большой вход (хотя бы по структуре)

случаи «все одинаковые», «строго возрастающий», «строго убывающий» (для массивов)

случаи, где ответ отсутствует

случаи, где ответов много

Полезная привычка: придумать контрпример к собственной идее. Если нашли — отлично, значит вы сэкономили попытку.

Частые ошибки на секции и как их избегать

Игнорирование ограничений. Решение кажется правильным, но не проходит по времени. Лекарство: сначала оценка сложности, потом код.

Слишком ранняя оптимизация. Погоня за микроскоростью вместо смены алгоритма. Лекарство: ищите снижение порядка сложности, а не «ускорение цикла».

Неучёт крайних случаев. Пустой массив, один элемент, повторяющиеся значения, отрицательные числа. Лекарство: чек-лист + тесты.

Нечёткая постановка. Вы решаете не ту задачу. Лекарство: переформулировка и маленький пример руками.

Как эта статья связывает курс

Дальше мы будем изучать алгоритмы и структуры данных как библиотеку решений. Но каждый раз вы будете начинать одинаково:

ограничения -> допустимые сложности

узкое место -> выбор техники (хеш, сортировка, два указателя, BFS/DFS, DP)

доказательство корректности -> реализация -> тесты

Если довести этот протокол до автоматизма, сложные темы курса начнут «складываться» быстрее и надёжнее.

Рекомендуемый справочник по Big-O

О-нотация (Big O notation) — Википедия

Массивы, строки и хеш-таблицы: частые приёмы

В прошлой статье курса мы зафиксировали «протокол решения»: ограничения допустимая сложность выбор техники инварианты реализация тесты. В этой статье разбираем самый частый набор инструментов алгоритмической секции: массивы, строки и хеш-таблицы.

Эти темы встречаются настолько часто, что цель — довести их до автоматизма: вы должны узнавать паттерн по формулировке и сразу доставать «правильную заготовку».

Базовые структуры и их роль

Массив

Массив — это последовательность элементов с доступом по индексу.

Типичные операции:

Пройти один раз и посчитать что-то: .

Отсортировать: обычно .

Взять подотрезок: почти всегда требует либо префиксных сумм, либо двух указателей.

Строка

Строка — частный случай массива символов, но задачи по строкам часто про:

частоты символов

сравнение подстрок по свойству (анаграмма, палиндром, уникальность)

«окно» по строке (скользящее окно)

Хеш-таблица

Хеш-таблица (в коде обычно dict / unordered_map / HashMap) хранит пары ключ-значение и даёт быстрый доступ по ключу.

В interview-модели считаем:

вставка и поиск в среднем

память , где — число различных ключей

Когда хеш-таблица особенно полезна:

нужно быстро проверять «видели ли элемент раньше»

нужно считать частоты значений

нужно хранить соответствие «значение позиция/счётчик/лучший результат»

Полезный справочник: Хеш-таблица — Википедия.

Паттерн «множество seen»: поиск дубликатов и пересечений

Формулировки, которые почти всегда ведут к хеш-множеству:

«есть ли повторяющиеся элементы»

«найдите первый повтор»

«проверить, встречалось ли значение ранее»

«пересечение двух массивов»

Идея:

заводим множество seen

идём по массиву

если элемент уже в seen, нашли ответ

иначе добавляем

Сложность:

время

память в худшем случае

Типичная ошибка:

пытаться сделать это через вложенные циклы при до

Паттерн «частоты»: счётчики и гистограммы

Очень частые вопросы:

«какое число встречается чаще всего»

«сколько раз встречается каждое значение»

«содержит ли строка одинаковое число букв»

«являются ли две строки анаграммами»

Есть два варианта реализации:

массив частот, если ключи маленькие и плотные (например, буквы a..z)

хеш-таблица, если ключи большие или разреженные (например, произвольные числа)

Практическое правило:

алфавит размера 26 или 256 обычно выгодно считать массивом

большие целые или строки — через хеш-таблицу

Префиксные суммы: быстрые суммы на отрезке

Префиксная сумма — это предобработка, которая превращает запрос «сумма на отрезке» в .

Определение

Пусть дан массив длины .

Заведём массив префиксов :

-

— сумма первых элементов массива

Формула построения:

Где:

— количество взятых элементов

— сумма первых элементов

— следующий добавляемый элемент (индексация в массивах часто с нуля)

Тогда сумма на полуинтервале равна:

Где:

— сумма первых элементов

— сумма первых элементов

разность даёт сумму элементов с индексами от до

!Диаграмма того, как префиксы позволяют получать сумму отрезка одной разностью

Где это применяют

много запросов суммы на отрезке

проверка условий на подотрезках

подготовка для более сложных трюков с хеш-таблицей (следующий раздел)

Частая ловушка

Префиксы сами по себе не отвечают на вопросы вида «найдите лучший/длиннейший подотрезок», если нет монотонности. Но они часто становятся «сырьём», а ответ ищется через хеш-таблицу.

«Подотрезки и сумма K»: префиксы + хеш-таблица

Один из самых частых паттернов секции:

«сколько подотрезков имеют сумму »

«найдите подотрезок с суммой »

«найдите максимальную длину подотрезка с суммой »

Ключевая идея:

сумма подотрезка равна

хотим

значит для текущего нам нужен такой , что

То есть мы идём по слева направо и храним в хеш-таблице, сколько раз встречались значения префикса .

Эффект:

вместо перебора всех пар за получаем по времени

Где часто ошибаются:

забывают инициализировать частоту префикса как 1 (это нужно, чтобы корректно считать подотрезки, начинающиеся с нулевого индекса)

Два указателя и скользящее окно

Паттерн «два указателя» — это способ превратить перебор всех подотрезков в один линейный проход, но работает он не всегда.

Когда это работает

Окно «расширяем вправо и при необходимости сжимаем слева» работает, когда есть монотонность:

если при движении правой границы условие становится «хуже», то движение левой границы делает его «лучше»

Самый частый случай:

массив неотрицательных чисел

условие про сумму, например «сумма окна »

Тогда:

двигаем правый указатель, добавляем элемент

пока условие нарушено, двигаем левый, убираем элементы

каждую границу двигаем не более раз, значит суммарно

!Наглядный принцип работы sliding window и почему он даёт O(n)

Где использовать

«минимальная длина подотрезка с суммой » при неотрицательных

«максимальная длина подотрезка с суммой » при неотрицательных

по строкам: «самая длинная подстрока без повторов» (с хеш-таблицей индексов)

Где нельзя использовать

если в массиве есть отрицательные числа, сумма окна уже не ведёт себя монотонно

тогда часто переходят к «префиксы + хеш-таблица» или другим техникам

Сортировка + два указателя: сумма пары и похожие задачи

Очень типовая развилка:

без сортировки: seen по дополнению до суммы даёт и возвращает факт/пару

с сортировкой: сортируем и работаем двумя указателями для задач на пары/тройки, получая на сортировку и на проход

Когда сортировка особенно удобна:

нужно вывести пары в отсортированном виде

нужно избегать дубликатов (после сортировки это проще)

задача расширяется до трёх элементов (например, «сумма трёх») и нужен системный контроль повторов

Строки: частые приёмы

Частоты символов

Самый частый приём для строк:

считаем частоты символов

сравниваем частоты

Примеры задач:

анаграммы

«можно ли переставить символы так, чтобы получилось…»

«какие символы встречаются чаще всего»

Если сказано «только строчные латинские буквы», почти всегда лучший выбор — массив длины 26.

Скользящее окно по строке

Строковые формулировки для окна:

«самая длинная подстрока без повторяющихся символов»

«самая длинная подстрока, где не больше различных символов»

«есть ли подстрока, являющаяся анаграммой образца»

Типовая техника:

два указателя l и r

структура для состояния окна (частоты или последний индекс)

при нарушении условия двигаем l, пока условие снова не выполнено

Отдельно полезный трюк:

хранить last_pos[c] — последний индекс, где встречался символ c

тогда при повторе символа можно прыгать l сразу, а не сдвигать по одному

Строки и хеш-таблицы

Хеш-таблица в строках появляется, когда:

алфавит большой (например, Unicode или произвольные токены)

нужно хранить соответствие «символ/слово счётчик/индекс»

Практика реализации: что важно на секции

Аккуратно выбирайте типы для сумм: суммы на элементов по легко выходят за 32-битный int.

Проверяйте крайние случаи: пустая строка, один символ, все символы одинаковые.

Для частот маленького алфавита используйте массив: он проще, быстрее и предсказуемее по памяти.

В задачах «подотрезки и сумма » не забудьте базовый префикс .

Мини-чеклист выбора техники

Нужно быстро проверить наличие элемента: множество.

Нужно посчитать частоты: хеш-таблица или массив частот.

Нужно много раз брать сумму на отрезке: префиксные суммы.

Нужно подотрезки с условием на сумму, и числа неотрицательные: скользящее окно.

Нужно подотрезки с суммой при возможных отрицательных: префиксы + хеш-таблица.

Нужно работать с парами после упорядочивания: сортировка + два указателя.

Эти приёмы закрывают значительную долю задач начального и среднего уровня на алгоритмической секции. Дальше по курсу мы будем добавлять к ним поиск (включая двоичный поиск по ответу) и базовые графовые обходы, но фундамент «массивы-строки-хеши» должен работать без пауз.

Два указателя, скользящее окно и префиксные суммы

В предыдущих статьях курса мы зафиксировали рабочий протокол решения задач (ограничения сложность техника инварианты код тесты) и разобрали базовые инструменты: массивы, строки и хеш-таблицы. Теперь соберём в одну «боевую связку» три приёма, которые на алгоритмической секции встречаются постоянно:

два указателя

скользящее окно (частный случай двух указателей)

префиксные суммы

Главная цель статьи: научиться по формулировке задачи быстро понять, что применимо, и не перепутать случаи, когда окно работает, а когда оно ломается.

Два указателя как идея

Два указателя — это техника, когда вместо вложенных циклов по массиву/строке вы поддерживаете две границы диапазона и двигаете их по определённым правилам.

Чаще всего указатели обозначают так:

l — левая граница

r — правая граница

В зависимости от задачи диапазон может означать:

текущее окно (подотрезок) или

пару элементов (например, в отсортированном массиве)

Ключ к корректности — инвариант: утверждение, которое остаётся истинным после каждого сдвига.

Скользящее окно

Скользящее окно — это самый частый вариант двух указателей для задач про подотрезки/подстроки.

Идея:

расширяем окно, двигая r вправо

если условие нарушилось, сжимаем окно, двигая l вправо

Важно: чтобы это работало за , нужно, чтобы выполнялась монотонность.

Когда окно работает

Окно обычно применимо, когда:

при увеличении r условие может стать хуже

при увеличении l условие может стать лучше

и это поведение предсказуемо

Самый типичный случай:

элементы массива неотрицательные

условие связано с суммой или чем-то похожим на «нагрузку окна»

Примеры формулировок:

«найдите минимальную длину подотрезка с суммой » (неотрицательные)

«найдите максимальную длину подотрезка с суммой » (неотрицательные)

«самая длинная подстрока, в которой не больше различных символов»

![Иллюстрация механики sliding window и сдвигов границ

Базовый шаблон окна

Ниже — универсальный каркас. В реальной задаче вы подставляете своё условие и своё «состояние окна» (например, сумму или частоты символов).

Что важно в этом каркасе:

r проходит массив один раз слева направо

l тоже движется только вправо и суммарно сделает не больше шагов

поэтому общая сложность по времени — , если add/remove/ok работают за

Пример: минимальная длина подотрезка с суммой (неотрицательные)

Дано:

массив неотрицательных чисел a

число S

Нужно:

минимальную длину подотрезка, сумма которого не меньше S

Инвариант:

на момент обновления ответа текущее окно уже имеет сумму

а перед этим мы сдвигали l максимально вправо, чтобы окно стало как можно короче

Реализация:

Почему тут нужна неотрицательность:

когда вы двигаете l вправо, сумма окна гарантированно не увеличивается

значит условие «сумма » действительно «улучшается» при сжатии окна

Пример: самая длинная подстрока без повторов

Здесь тоже два указателя, но «состояние окна» — это информация о символах.

Классический вариант:

храним last_pos[c] — последнюю позицию символа c

если c встречался внутри текущего окна, прыгаем l вперёд

Инвариант:

подстрока s[l..r] всегда содержит уникальные символы

Когда скользящее окно не подходит

Главная причина провала окна — отсутствие монотонности.

Типичный «красный флаг»:

в массиве есть отрицательные числа

а условие связано с суммой

Почему это ломает окно:

вы расширили окно вправо, сумма стала больше

но следующий добавленный элемент может быть отрицательным и сумма внезапно уменьшится

значит «сжимать слева, пока плохо» перестаёт быть корректной стратегией

В таких задачах часто нужно переключаться на префиксные суммы и иногда добавлять хеш-таблицу.

Префиксные суммы

Префиксная сумма — это предобработка массива, которая позволяет быстро получать сумму на отрезке.

Определение и формула

Пусть дан массив длины .

Строим массив префиксов длины :

— сумма «первых нуля элементов»

— сумма первых элементов массива

Формула построения:

Пояснение каждого элемента формулы:

— сколько первых элементов массива мы суммируем

— сумма первых элементов

— следующий элемент, который добавляем к сумме

индексация i-1 появляется из-за того, что в массивах обычно первый элемент имеет индекс 0

Сумма на полуинтервале (то есть элементы с индексами l, l+1, ..., r-1) считается так:

Здесь:

— сумма первых элементов

— сумма первых элементов

их разность оставляет сумму элементов от l до r-1

Пример построения

Типичные применения:

много запросов суммы на отрезке

«есть ли подотрезок с суммой …»

«сколько подотрезков имеют сумму …» (обычно вместе с хеш-таблицей)

Справочник: Prefix sums — CP-Algorithms.

Подотрезки с суммой K: префиксы + хеш-таблица

Один из самых повторяемых паттернов секции:

«сколько подотрезков имеют сумму »

Если пытаться перебирать все пары границ , будет .

С префиксами:

сумма подотрезка равна

хотим

значит нужно, чтобы

Алгоритм:

идём по слева направо

поддерживаем хеш-таблицу cnt, где cnt[value] — сколько раз мы уже встречали такой префикс

для текущего префикса p[r] добавляем к ответу cnt[p[r] - K]

Критически важная инициализация:

cnt[0] = 1, потому что префикс 0 «встречен» до начала массива

иначе вы потеряете подотрезки, начинающиеся с нулевого индекса

Код:

Почему это работает и при отрицательных числах:

мы не используем монотонность

мы используем точное равенство через префиксы и быстрый поиск через хеш-таблицу

Как выбрать технику на задаче

Ниже — практичная «развилка» по формулировке.

| Формулировка/свойство | Обычно подходит | Почему | |---|---|---| | Подотрезок, условие на сумму, все числа неотрицательные | скользящее окно | монотонность при движении l и r | | Подотрезок, условие на сумму, есть отрицательные | префиксы + хеш | окно теряет корректность | | Много запросов суммы на отрезке | префиксы | один раз предобработали, запрос | | Подстроки с ограничением на символы (уникальность, разных) | окно + частоты/позиции | состояние окна обновляется локально |

Справочник по идее двух указателей: Two pointers technique — CP-Algorithms.

Частые ошибки и как их предотвращать

Перепутали границы и

Забыли cnt[0] = 1 в задачах на сумму

Применили окно при отрицательных числах и получили неверный ответ

Не продумали инвариант и «двигаете указатели наугад»

Переполнение суммы: если значения до , сумма может не влезть в 32-битный тип

Если вы можете вслух ответить на два вопроса, шанс на правильное решение резко растёт:

почему условие монотонно (или почему оно не нужно)?

какой инвариант сохраняется при каждом сдвиге границ?

Эти техники закрывают большую долю задач на массивы и строки в алгоритмической секции. В следующих темах курса они будут использоваться как «строительные блоки» вместе с двоичным поиском и графовыми обходами.

Стеки, очереди, deque и монотонные структуры

В предыдущих статьях мы опирались на линейные проходы, два указателя, скользящее окно, префиксные суммы и хеш-таблицы. На алгоритмической секции очень часто встречаются задачи, где данные приходят потоком, а решение нужно поддерживать на лету. Здесь особенно полезны структуры с операциями на добавление и удаление:

стек

очередь

deque (двусторонняя очередь)

монотонные структуры (монотонный стек и монотонный deque)

Ключевая цель этой темы: узнавать формулировки вроде "ближайший больший справа", "минимум на каждом окне длины k", "проверить корректность скобок" и сразу доставать правильную структуру.

Стек

Стек — структура данных по принципу LIFO (last in, first out): последним положили, первым достали.

Базовые операции (в интервью-модели считаем их ):

push: положить элемент на вершину

pop: снять элемент с вершины

top/peek: посмотреть вершину

Справочник: Стек — Википедия.

Как узнать задачу под стек

Частые формулировки:

"проверить корректность скобочной последовательности"

"отменить последнее действие", undo

"обработать выражение" (постфиксная запись, стек операций)

"удаляем/схлопываем, пока условие нарушено"

Пример паттерна: корректность скобок

Инвариант: в стеке лежат не закрытые открывающие скобки.

Алгоритм:

идём по строке слева направо

если символ открывающий, кладём в стек

если закрывающий, проверяем, что стек не пуст и верх подходит, затем снимаем

в конце стек должен быть пуст

Важные ошибки:

забыть проверить пустоту стека перед pop

не учесть несколько видов скобок

Очередь

Очередь — структура по принципу FIFO (first in, first out): первым пришёл, первым ушёл.

Базовые операции (обычно ):

push/enqueue: добавить в конец

pop/dequeue: убрать из начала

front: посмотреть первый

Справочник: Очередь (структура данных) — Википедия).

Где очередь появляется на секции

Очередь часто всплывает в задачах на:

симуляцию процессов ("обслуживание клиентов", "печать задач")

обходы в ширину (BFS) — это будет особенно важно, когда вы дойдёте до графов

Deque (двусторонняя очередь)

Deque — это очередь, где можно добавлять и удалять элементы с обоих концов.

Операции (обычно ):

добавить в начало / удалить из начала

добавить в конец / удалить из конца

Справочник: Deque — Википедия.

Зачем нужен deque, если есть очередь

Deque становится критически полезен, когда нужно:

поддерживать окно (как в скользящем окне), но уметь быстро выкидывать элементы и слева, и справа

хранить кандидатов на минимум/максимум так, чтобы «плохие» кандидаты удалялись сразу

Это приводит нас к монотонным структурам.

Монотонный стек

Монотонный стек — это стек, в котором элементы (чаще индексы) лежат так, что значения на них идут монотонно.

Зачем: решать задачи вида "для каждого элемента найти ближайший слева/справа больший/меньший" за один проход.

Типовые задачи

следующий больший элемент справа (next greater element)

предыдущий меньший слева

границы, где элемент является минимумом (подготовка к задачам вроде «максимальный прямоугольник», если дойдёте до них)

Как устроен проход

Идея: если новый элемент делает часть предыдущих элементов «бесполезными», мы их снимаем.

Например, для "следующий больший справа" удобно держать стек индексов с убывающими значениями:

пока текущий элемент больше, чем элемент на вершине, значит мы нашли ответ для вершины

снимаем вершину и записываем ответ

затем кладём текущий индекс

!Монотонный стек на примере поиска следующего большего элемента справа

Важные детали реализации

чаще хранят индексы, а не значения

нужно заранее решить, как обрабатывать равные элементы: условие в цикле будет while a[stack_top] < a[i] или <= в зависимости от того, что считается "большим"

инвариант нужно уметь проговорить: "значения по индексам в стеке строго убывают" (или нестрого)

Монотонный deque

Монотонный deque — это двусторонняя очередь индексов, где значения поддерживаются монотонно. Самое частое применение: минимум или максимум на каждом окне фиксированной длины .

Задача-паттерн: минимум на каждом окне длины k

Дано:

массив a

размер окна k

Нужно вывести минимум для каждого окна: a[i..i+k-1].

Лобовое решение:

для каждого окна искать минимум за

итого , что не проходит при больших ограничениях

Монотонный deque делает это за линейное время.

Инвариант монотонного deque для минимума

Будем хранить индексы элементов, кандидатов на минимум текущего окна.

Инвариант:

индексы в deque идут слева направо по возрастанию (это просто из-за движения по массиву)

значения a[indices] в deque идут по возрастанию, то есть в начале стоит текущий минимум

Алгоритм

Для каждого нового индекса r:

Удаляем индексы, которые вышли из окна (они слишком слева).

Пока хвост deque имеет значение больше текущего a[r], удаляем хвост: такой элемент уже никогда не станет минимумом, потому что справа пришёл меньший.

Добавляем r в хвост.

Когда окно уже набрано (то есть r >= k-1), минимум — это a[deque[0]].

!Монотонный deque для минимума на каждом окне

Почему это работает быстро

Каждый индекс:

добавляется в deque ровно один раз

удаляется из deque не более одного раза (либо из головы по выходу из окна, либо из хвоста как "побеждённый" более выгодным элементом)

Поэтому суммарно операций на все push/pop получается линейно от размера массива.

Аккуратность с равными значениями

Как и в монотонном стеке, нужно решить политику равенства:

если вы удаляете из хвоста по условию a[tail] > a[r], то равные останутся, и минимум будет самым левым из равных

если удаляете по a[tail] >= a[r], то равные будут «схлопываться», и минимум будет ближе к правой границе

Оба варианта могут быть корректны, но важно, чтобы это не ломало требование задачи (например, если нужно выбрать самый левый минимум).

Практика: как это обычно кодят

Python

стек: обычный список list с append и pop

очередь и deque: collections.deque

C++

стек часто делают на vector (быстрее и проще)

очередь/двусторонняя очередь: std::deque или std::queue

Типовые ошибки на секции

путаница индексов окна: где левая граница, когда элемент считается вышедшим

хранение значений вместо индексов там, где нужно выкидывать по позиции (окна)

неверное условие на равенство (< против <=), из-за чего ломаются ответы на массивах с повторами

попытка сделать окно-минимум через кучу (priority queue), забыв, что из кучи трудно быстро удалять элементы, вышедшие из окна (это возможно, но требует дополнительной логики)

Мини-чеклист выбора структуры

нужно обрабатывать вложенность или последний открытый элемент: стек

нужно обработать элементы в порядке прихода: очередь

нужно окно и операции с двух концов: deque

нужно ближайший больший/меньший слева/справа: монотонный стек

нужно минимум/максимум на каждом окне фиксированной длины: монотонный deque

Эти структуры отлично дополняют скользящее окно из предыдущей статьи: теперь вы умеете не только двигать границы, но и поддерживать внутри окна нужную характеристику (минимум/максимум) без пересчёта с нуля.

Двоичный поиск и техники поиска ответа

В прошлых темах курса мы учились превращать «перебор всего» в линейные решения с помощью хеш-таблиц, префиксных сумм, двух указателей, стеков и монотонных структур. Но на алгоритмической секции очень часто встречается другой тип оптимизации:

мы не перебираем все варианты ответа

мы делаем проверку «подходит ли кандидат»

и с помощью двоичного поиска быстро находим границу, где ответ меняется

Это называется поиск по ответу (binary search on answer) и обычно даёт выигрыш от или к или .

Идея двоичного поиска

Двоичный поиск применяется, когда есть отсортированность или монотонность.

Два самых частых случая:

Поиск в отсортированном массиве: хотим найти элемент или позицию вставки.

Поиск по ответу: массив может быть не отсортирован, но есть функция-проверка ok(x), которая монотонна по .

Под монотонностью здесь понимается простое свойство:

либо ok(x) ложно для малых и становится истинным начиная с некоторой границы

либо наоборот, истинно на малых и становится ложным после границы

!Схема того, как двоичный поиск сужает диапазон и ищет границу true/false

Классический двоичный поиск в отсортированном массиве

Что именно обычно ищут

На практике на секции чаще всего нужен не «нашли/не нашли», а граница:

lower_bound: первый индекс, где значение

upper_bound: первый индекс, где значение

Эти два варианта удобно использовать для:

подсчёта количества элементов, равных

поиска места вставки

поиска первого подходящего элемента

Почему «границы» важнее, чем «нашли элемент»

Потому что при повторах «любой индекс с » часто бесполезен. Например, чтобы посчитать, сколько раз встречается в отсортированном массиве:

находим lb = lower_bound(x)

находим ub = upper_bound(x)

ответ равен

Здесь и — индексы. Разность означает «сколько позиций между границами».

Шаблон lower_bound (первый индекс, где )

Инвариант, который держим во время поиска:

слева остаются точно неподходящие индексы

справа остаются кандидаты, среди которых есть ответ

Удобный и устойчивый к ошибкам вариант — поиск по полуинтервалу :

l включаем

r не включаем

Что возвращается:

индекс от 0 до n

если все элементы меньше , вернётся n (то есть «позиция после конца»)

Шаблон upper_bound (первый индекс, где )

Разница только в условии сравнения.

Поиск по ответу: двоичный поиск по монотонной проверке

Как узнать задачу «под поиск по ответу»

Формулировки, которые почти всегда сигналят этот подход:

«найдите минимальное , такое что условие выполняется»

«какой наименьший/наибольший параметр можно выбрать»

«можно ли сделать за времени/дней/ресурсов»

«минимальный максимальный…» (классика распределения и разбиений)

Здесь ключевое: мы можем быстро проверить ok(X), но перебор всех слишком дорог.

Как устроен каркас решения

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

Пишем проверку ok(X) со сложностью обычно или .

Доказываем монотонность:

- если ok(X) истинно, то ok(X+1) тоже истинно (или аналогично в другую сторону).

Запускаем двоичный поиск по диапазону .

Важно: двоичный поиск не делает алгоритм быстрым сам по себе. Быстрота получается из произведения:

число проверок

стоимость одной проверки

Если проверка дорогая, итог тоже будет дорогим.

Примерный шаблон: найти минимальный , для которого ok(X)=true

Пусть:

ok(x) возвращает True, если параметр достаточно большой, чтобы условие выполнялось

нам нужен минимальный

Тогда двоичный поиск:

Пояснение переменных:

lo и hi — границы диапазона возможных ответов

mid — середина диапазона

Почему цикл заканчивается:

на каждом шаге диапазон строго сужается

в итоге lo == hi, и это и есть минимальный подходящий кандидат

Как выбирать границы поиска

Выбор границ — источник многих багов. Практичные правила:

lo должен быть заведомо слишком маленьким (условие ещё не выполнено) или просто нижней границей по смыслу

hi должен быть заведомо достаточно большим (условие выполнено) или верхней границей по смыслу

Если вы ищете «минимальный », полезно обеспечить:

ok(hi) == True

Если вы ищете «максимальный », полезно обеспечить:

ok(lo) == True

Типичный приём, если не знаете верхнюю границу:

начинаете с hi = 1

удваиваете hi, пока ok(hi) не станет истинным

Это даёт логарифмическое число расширений диапазона.

Пример задачи: «разрезать на не более чем k кусочков» (поиск по ответу)

Типовая форма:

дан массив величин (например, длины, веса, объёмы)

хотим минимизировать максимальную нагрузку на группу

есть ограничение на число групп

Классический пример: минимизировать максимальную сумму сегмента при разбиении массива на частей.

Что такое кандидат :

предполагаем, что максимальная допустимая сумма одного сегмента равна

Что такое ok(X):

можно ли разбить массив на не более чем сегментов так, чтобы сумма каждого сегмента была

Почему проверка монотонна:

если можно при , то при большем тоже можно, потому что ограничения ослабли

Как обычно пишется ok(X):

идём слева направо

набираем текущий сегмент

если добавление элемента превышает , начинаем новый сегмент

считаем, сколько сегментов получилось

Сложность проверки:

один проход по массиву:

Итог:

двоичный поиск делает около проверок, где — диапазон сумм

общая сложность:

Как комбинировать двоичный поиск с техниками из прошлых тем

Двоичный поиск почти всегда «сидит снаружи», а внутри ok(x) используются уже знакомые инструменты.

Частые комбинации:

двоичный поиск + префиксные суммы: быстро считать суммы/стоимости для проверки

двоичный поиск + два указателя: если в проверке нужно «можно ли уложиться при ограничении » и есть монотонность

двоичный поиск + монотонный deque/стек: реже, но бывает, когда проверка требует поддерживать экстремумы в окнах

двоичный поиск + сортировка: например, проверка делает жадный проход по отсортированным данным

Главная дисциплина: держать проверку простой и гарантированно корректной.

Типичные ошибки и как их предотвращать

Неправильная монотонность: вы думаете, что ok(x) монотонна, но есть контрпример. Лекарство: явно проговорить «если ok(x) истинно, почему ok(x+1) тоже истинно?».

Ошибка в границах: забыли включительность/исключительность. Лекарство: придерживаться шаблонов на или строго фиксировать, что ищете «первый true».

Бесконечный цикл: особенно в вариантах, где среднее округляется вниз и границы не двигаются. Лекарство: использовать проверенные каркасы, где при False делаете lo = mid + 1.

Переполнение mid: в языках с 32-битными целыми mid = (l + r) / 2 может переполниться. Лекарство: mid = l + (r - l) / 2.

Слишком медленная проверка: если ok(x) внутри делает и ещё вызывается раз, итог может быть слишком большим. Лекарство: оптимизировать именно проверку.

Мини-чеклист: когда двоичный поиск — правильный инструмент

Есть отсортированный массив и нужно найти позицию/границу: lower_bound/upper_bound.

Нужно минимальное/максимальное значение параметра: почти наверняка поиск по ответу.

Есть функция ok(x) и вы уверены в монотонности: двоичный поиск по предикату.

Рекомендуемые источники

[Двоичный поиск — Википедия

Binary Search — CP-Algorithms

Деревья, кучи и базовые алгоритмы на графах

В предыдущих статьях курса мы учились ускорять решения за счёт правильных структур данных и паттернов: хеш-таблицы, префиксные суммы, два указателя, стек/очередь/deque, монотонные структуры, двоичный поиск по ответу. Следующий большой пласт задач алгоритмической секции — деревья и графы.

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

представление графа в памяти

обходы DFS и BFS

поиск компонент связности

проверка циклов и базовые свойства

топологическая сортировка в DAG

куча и Дейкстра для кратчайших путей с неотрицательными весами

!Сравнение дерева, графа и кучи и как они выглядят

Базовые определения: граф, дерево, ориентированность

Граф состоит из:

множества вершин (узлов)

множества рёбер (связей)

Граф бывает:

неориентированный: ребро связывает две вершины в обе стороны

ориентированный: ребро идёт из в и направление важно

взвешенный: у ребра есть вес (стоимость, длина)

Дерево — это связный неориентированный граф без циклов. Важное свойство дерева:

если в дереве вершин, то рёбер ровно

Обходы графа почти всегда требуют структуры из прошлой статьи:

DFS естественно реализуется стеком (часто рекурсией, которая по сути тоже стек)

BFS реализуется очередью

Справочные источники:

Граф (математика) — Википедия)

Дерево (теория графов) — Википедия)

Как хранить граф: список смежности против матрицы

На секции почти всегда выбирают список смежности.

Список смежности

Идея:

для каждой вершины храним список соседей

Память:

, где — число вершин, — число рёбер

Плюсы:

эффективен для разреженных графов

удобно запускать BFS/DFS

Матрица смежности

Идея:

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

Память:

-

Минус:

при порядка это невозможно по памяти

Практическое правило:

если граф большой, почти наверняка нужен список смежности

| Представление | Память | Проверка ребра | Перебор соседей вершины | |---|---:|---:|---:| | Список смежности | | обычно | | | Матрица смежности | | | |

DFS: поиск в глубину

DFS (depth-first search) — обход, который идёт вглубь, пока может.

Типовые применения:

проверить достижимость (есть ли путь)

найти компоненты связности

обнаружить цикл

сделать топологическую сортировку (в ориентированном ациклическом графе)

Инвариант DFS

вершина помечается как посещённая, и после этого мы больше не обходим её повторно

Итеративный DFS (стеком)

Итеративная версия часто надёжнее рекурсии на больших входах (например, в Python из-за ограничений глубины рекурсии).

Справочник:

Depth First Search — CP-Algorithms

BFS: поиск в ширину и кратчайшие пути в невзвешенном графе

BFS (breadth-first search) — обход слоями: сначала все вершины на расстоянии 1 ребро, потом 2 ребра и так далее.

Ключевой факт для задач:

в невзвешенном графе BFS даёт кратчайшее расстояние по числу рёбер

Инвариант BFS

когда вершина впервые извлекается из очереди, найдено её минимальное расстояние (в рёбрах) от старта

Код BFS для расстояний

Где в коде зашита математика:

dist[start] = 0 означает расстояние от старта до себя равно 0

dist[to] = dist[v] + 1 означает: мы пришли в to по одному ребру из v, поэтому расстояние увеличилось на 1

Справочник:

Breadth First Search — CP-Algorithms

!BFS идёт слоями и даёт кратчайшие расстояния по числу рёбер

Компоненты связности в неориентированном графе

Частая формулировка:

«сколько компонент связности?»

«разбейте вершины на группы достижимости»

Решение:

идём по всем вершинам

если вершина не посещена, запускаем DFS/BFS и помечаем всю её компоненту

Сложность:

, потому что каждая вершина посещается максимум один раз, и каждое ребро рассматривается ограниченное число раз

Деревья как частный случай графов

В дереве нет циклов, и это упрощает многие вещи.

Корневое дерево и родитель

Часто дерево «укореняют» в вершине root. Тогда:

у каждой вершины (кроме корня) есть родитель

можно считать глубины (depth) и поддеревья

BFS/DFS на дереве

Они работают так же, как на графе, но для дерева важная оптимизация мыслительная:

если мы пришли из parent в v, то обратно по ребру к parent идти не надо

В коде это часто выглядит так:

либо используем visited

либо передаём parent и пропускаем его

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

Куча (priority queue): быстрый доступ к минимуму/максимуму

Куча — структура данных для операций:

вставить элемент

достать элемент с минимальным (или максимальным) ключом

Типичная модель сложности:

вставка:

извлечение минимума:

посмотреть минимум:

Почему появляется логарифм:

куча поддерживает частичный порядок, и на восстановление свойств после вставки/удаления нужно подняться или спуститься по высоте дерева, а высота порядка

Справочники:

Двоичная куча — Википедия

Priority queue — Википедия

Типовые задачи под кучу

«всегда брать текущий минимальный элемент»

«сделать раз: взять лучшее, обновить, вернуть обратно»

«слить несколько отсортированных потоков»

«кратчайший путь во взвешенном графе»

Минимальная куча в Python

Практическая деталь:

часто кладут пары (приоритет, вершина) или (стоимость, состояние)

!Куча как дерево и как массив

Дейкстра: кратчайшие пути с неотрицательными весами

Формулировки, которые почти всегда ведут к Дейкстре:

«найдите кратчайший путь»

«минимальная стоимость добраться из A в B»

«граф взвешенный, веса неотрицательные»

Ключевое ограничение:

веса рёбер должны быть неотрицательными, иначе стандартная Дейкстра может дать неверный ответ

Идея алгоритма

Мы поддерживаем текущие лучшие расстояния dist[v] и всегда выбираем вершину с минимальным dist среди ещё не обработанных. Это ровно то, что удобно делать кучей.

Что означает формула релаксации

Если есть ребро веса , то кандидат на улучшение:

Пояснение каждого элемента:

— уже найденная стоимость добраться до вершины

— стоимость перейти по ребру из в to

сумма — стоимость маршрута, который сначала идёт до , а потом делает один шаг в to

Если new меньше текущего dist[to], мы улучшаем ответ.

Код Дейкстры (список смежности с весами)

Предполагаем, что g[v] — список пар (to, w).

Критически важная проверка if d != dist[v]:

в кучу могут попасть устаревшие записи

мы пропускаем их, чтобы не делать лишнюю работу

Сложность в типичной оценке:

из-за операций кучи

Справочник:

Dijkstra Algorithm — CP-Algorithms

Топологическая сортировка: порядок выполнения в DAG

Формулировки, которые почти всегда означают топологическую сортировку:

«есть зависимости между задачами»

«нужно упорядочить так, чтобы каждое ребро шло слева направо»

«найдите порядок курсов с пререквизитами»

Топологическая сортировка существует только если ориентированный граф ацикличен (то есть это DAG).

Есть два классических подхода:

DFS с выходными временами

алгоритм Кана (через входные степени и очередь)

На секции часто проще и надёжнее алгоритм Кана.

Алгоритм Кана (очередь + входные степени)

Идея:

посчитаем indeg[v] — сколько рёбер входит в вершину v

все вершины с indeg = 0 можно ставить первыми

удаляем их из графа (уменьшая indeg соседей), и процесс продолжается

Как понять, что есть цикл:

если мы не смогли извлечь все вершины (очередь опустела слишком рано), значит остались вершины с indeg > 0, то есть цикл

Справочник:

Topological Sorting — CP-Algorithms

Частые ошибки на секции

Путают представление графа: делают матрицу смежности при больших и ловят MLE.

Забывают visited или метку расстояния и получают бесконечные обходы по циклам.

В BFS неправильно инициализируют dist и теряют недостижимые вершины.

Запускают Дейкстру при отрицательных весах.

В Python используют рекурсивный DFS на длинной цепочке и получают ошибку глубины рекурсии.

В Дейкстре не отбрасывают устаревшие элементы из кучи и получают лишнюю работу.

Мини-чеклист выбора техники

Граф невзвешенный, нужен кратчайший путь в рёбрах: BFS.

Граф, нужно просто обойти, найти компоненты, проверить достижимость: DFS/BFS.

Веса неотрицательные, нужен кратчайший путь по стоимости: Дейкстра + куча.

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

Структура ввода — дерево: обычно достаточно DFS/BFS, иногда с параметром parent.

Эти темы логично продолжают предыдущие статьи курса: очередь и стек дают обходы, deque вы уже видели в окнах, а куча добавляет инструмент для задач, где нужно постоянно выбирать лучший следующий шаг. В сумме это покрывает значительную долю «графовой базы» алгоритмической секции.

Динамическое программирование и комбинирование паттернов

До этого в курсе мы почти всегда ускоряли решения так:

убирали вложенные циклы через хеш-таблицы, два указателя и префиксы

поддерживали состояние «на лету» через стек/очередь/deque

находили границу ответа через двоичный поиск

обходили графы BFS/DFS и искали кратчайшие пути (BFS/Дейкстра)

Динамическое программирование (DP) — следующий ключевой слой. Он появляется там, где:

решение для большого объекта можно выразить через решения для меньших

одни и те же подзадачи возникают много раз

нужно найти максимум/минимум/количество способов, а не просто факт существования

DP на алгоритмической секции Яндекса обычно проверяет не «теорию», а практику:

быстро выбрать корректное состояние

не ошибиться с переходом и базой

уложиться в , или по ограничениям

!Идея DP: разбиваем на подзадачи и переиспользуем результаты

Что такое динамическое программирование

DP — это техника, где мы заводим массив/таблицу dp и определяем:

состояние: что означает dp[...]

база: чему равны значения на самых маленьких входах

переход: как вычислить dp из уже известных меньших значений

порядок вычисления: в каком порядке заполнять dp, чтобы нужные значения уже были посчитаны

Практически полезное определение:

DP = рекуррентная формула + сохранение результатов

Два стиля реализации:

снизу вверх: заполняем dp циклом

сверху вниз: рекурсия + мемоизация (кэш)

На секции чаще выигрывает вариант снизу вверх: меньше накладных расходов и проще контролировать сложность.

Как распознать задачу под DP

Формулировки, которые часто ведут к DP:

«найдите максимальное/минимальное … на префиксе/на первых элементах»

«сколько способов …»

«можно ли …, используя первые элементов»

«оптимально разрезать/разбить/выбрать набор»

«минимальная стоимость добраться до конца, если шаги ограничены»

Сигнал, что DP особенно уместно:

наивное решение — это перебор вариантов с повторяющимися кусками

подзадачи перекрываются (одинаковое i, одинаковая позиция, одинаковая сумма и т.д.)

Протокол построения DP-решения

Состояние

Состояние должно отвечать на вопрос:

«какой кусок задачи я уже обработал и что я хочу о нём знать?»

Чаще всего это:

dp[i] для последовательностей

dp[i][j] для сеток/двух параметров

Важно: состояние должно быть достаточно информативным, чтобы из него сделать следующий шаг, но не слишком большим, чтобы не взорвать сложность.

База

База — это значения dp для самых маленьких случаев. Они нужны, чтобы переходы «зацепились».

Переход

Переход — локальное правило, как получить dp[current] из нескольких dp[previous].

Порядок

Порядок должен гарантировать:

когда мы считаем dp[current], все нужные dp[previous] уже известны

Обычно это означает движение по i слева направо (или по строкам/столбцам в таблице).

Сложность

Если переход перебирает много вариантов, быстро появляется лишний множитель.

Например:

dp[i] за для каждого i даёт

dp[i] за для каждого i даёт

dp[i] за для каждого i даёт

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

Базовый пример: «лестница» (минимальная стоимость)

Типовая задача:

есть массив стоимостей cost[i]

можно перейти из i-1 в i или из i-2 в i

нужно минимальную стоимость добраться до n-1

Состояние:

dp[i] = минимальная стоимость оказаться на ступеньке i

Переход:

Пояснение формулы:

dp[i] — ответ для позиции i

cost[i] — стоимость наступить на i

dp[i-1] и dp[i-2] — минимальные стоимости попасть на предыдущие ступени

\min(...) выбирает более выгодный способ прийти

База:

dp[0] = cost[0]

dp[1] = cost[1] + dp[0] (или отдельная логика, если старт допускает прыжок)

Код:

Оптимизация памяти

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

Это общий приём: если dp[i] зависит только от небольшой «полосы» прошлых состояний, память можно снизить с до .

DP на строках: расстояние редактирования как пример мышления

Задачи на строки часто превращаются в DP по двум индексам.

Пример формулировки:

«минимальное число операций, чтобы превратить строку a в строку b»

Здесь важна не конкретная формула, а принцип выбора состояния:

dp[i][j] = минимальная стоимость превратить префикс a[:i] в префикс b[:j]

Здесь:

i — сколько первых символов строки a мы уже учитываем

j — сколько первых символов строки b мы уже учитываем

Переходы обычно рассматривают «последний шаг»: что мы делали с последним символом.

На секции такие DP бывают, но чаще в упрощённых вариантах. Если видите два индекса и операции над символами, почти наверняка это dp[i][j].

!Типичный вид DP-таблицы по двум строкам

Рюкзак: почему важно следить за порядком

Классический паттерн:

есть предметы с весами и ценностями

нужно максимизировать ценность при ограничении по весу

Даже если вы не решаете «полный рюкзак» на секции, важно понимать один общий момент:

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

Это типовая ловушка DP: формула может выглядеть почти одинаково, но «направление цикла» меняет смысл.

Практическая привычка:

проговорить вслух, что означает dp[w] именно после обработки первых i предметов

Комбинирование паттернов: DP редко живёт в вакууме

На секции часто нужно не «просто DP», а DP, ускоренное или упрощённое другими техниками из курса.

DP + префиксные суммы

Ситуация:

переход для dp[i] использует сумму на отрезке, например «стоимость сегмента j..i»

Тогда вместо пересчёта суммы в каждом переходе:

строят префиксные суммы p

получают сумму отрезка за

Это превращает переход вида «перебрать j и быстро посчитать цену сегмента» в адекватный по константам.

DP + двоичный поиск

Два частых кейса:

нужно быстро найти место, куда можно «продолжить» решение (границу)

нужно поддерживать структуру, где значения упорядочены, и находить позицию вставки

Классический пример мышления — задача про наибольшую возрастающую подпоследовательность (LIS):

базовое DP даёт

оптимизация через двоичный поиск по массиву «лучших хвостов» даёт

На интервью обычно достаточно понимать идею:

мы не храним саму подпоследовательность

мы храним минимально возможный последний элемент для каждой длины

место обновления находим двоичным поиском (аналог lower_bound из прошлой статьи)

DP + монотонный deque (ускорение перехода)

Очень практичный паттерн:

переход выглядит как «взять минимум/максимум среди dp[j] на скользящем диапазоне j»

Пример:

Пояснение формулы:

dp[i] — лучшая стоимость прийти в i

a[i] — цена шага в i

мы выбираем, из какой из последних позиций прийти

нам нужен минимум среди dp[j] на окне индексов

Если считать минимум перебором, будет O(n)O(n^2)n=10^5O(n^2) \to O(n \log n)$ через поддержание упорядоченной структуры: DP + двоичный поиск.

Граф — DAG, и есть зависимости по рёбрам: DP по топологическому порядку.

Структура — дерево и ответ собирается из поддеревьев: tree DP через DFS.

Рекомендуемые источники

Dynamic Programming — Википедия

Introduction to Dynamic Programming — CP-Algorithms

Longest Increasing Subsequence — CP-Algorithms