Дом-грабитель
Грабить дома нельзя два подряд: взять или пропустить — два бегущих максимума.
1function rob(money: number[]): number {2 let prev2 = 0 // максимум до дома i-23 let prev1 = 0 // максимум до дома i-14 5 for (const m of money) {6 const take = prev2 + m // берём этот дом7 const skip = prev1 // пропускаем8 prev2 = prev19 prev1 = Math.max(take, skip)10 }11 12 return prev113}Проблема
Грабить дома нельзя два подряд: взять или пропустить — два бегущих максимума.
Что вы видите
Каждый дом подсвечивается решением, подпись best — лучший улов до этого дома.
Как это работает
best(i) = max(best(i−2)+деньги_i, best(i−1)): взять нельзя после соседа. Два скользящих значения, O(1) памяти. Схема «взять/пропустить с запретом соседей» — основа scheduling-задач.
Пошаговый разбор
- 01
Взять
Плюс деньги дома и i−2 назад.
- 02
Пропустить
Наследуем i−1.
- 03
Жадность врёт
Локально жирный дом ломает цепочку.
Complexity и ограничения
Сложность см. в шапке страницы.
Edge cases
- Пустой вход
Корректная тривиальная обработка.
- Вырожденный случай
Минимум работы — сразу ответ.
Где встречается в реальности
Расписание
Несовместимые во времени задачи = «нельзя соседние».
Выкуп дорог
Выбор несмежных сегментов трассы.
Реклама
Максимум выручки без подряд идущих слотов.
Связанные алгоритмы
«Нельзя два соседних: максимум улова»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.