Где применяется
1. Задача
Перед тобой ряд плиток. На каждой плитке одно число: самый длинный прыжок вперёд, который с неё можно сделать. С плитки с числом 3 можно шагнуть вперёд на 1, 2 или 3 плитки. С плитки с 0 сдвинуться нельзя. Ты стоишь на первой плитке. Дойдёшь ли до последней?
Возьми [2, 3, 1, 1, 4]. С плитки 0 можно прыгнуть на 1 или на 2 плитки вперёд. Прыгни на плитку 1. На ней стоит 3, и с неё ты допрыгнешь до конца. Ответ true.
Теперь возьми [3, 2, 1, 0, 4]. Как ни прыгай, дальше плитки 3 не уйти. На ней стоит 0. До 4 в конце не добраться. Ответ false.
В прошлом уроке про сдачу монетами мы на каждом шаге брали вариант, лучший на вид, и обосновывали, почему это безопасно. Здесь тот же жадный подход, только вопрос другой: дойдёшь ли ты до конца вообще.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- наименьшее число монет или частей на сумму
- берём самую крупную, что ещё помещается
- выдать сдачу номиналами
- доказать оптимальность обменным аргументом
Похоже, но не то
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Динамика держит все варианты открытыми до конца. Жадность выбирает сразу и не может откатиться.
- Бэктрекинг (Backtracking)
Бэктрекинг пробует все варианты и оставляет лучший. Жадность пробует один и ему верит.
- Сортировка с пользовательским компаратором (Sort with a custom comparator)
Большинство жадных решений начинается с сортировки. В компараторе и записан сам выбор.
- Бинарный поиск по ответу (Binary search on the answer)
Там сама проверка часто жадная. Поиск лишь выбирает значение для проверки.
O(n log n), если вход сначала нужно отсортировать. Проход после сортировки это один цикл, O(n).
На LeetCode
Задачи на прыжки и покрытие, где с каждой позиции можно дотянуться до какой-то точки, а спрашивают, дойдёшь ли ты до конца или за сколько шагов. Один проход, который хранит самую дальнюю достижимую позицию, отвечает за O(n).
Задача урока слово в слово.
Считай прыжок каждый раз, когда i доходит до конца зоны текущего прыжка, а следующая зона кончается на самой дальней позиции, увиденной до сих пор.
Для каждого начала запиши, докуда дотягивается клип, и подсчёт из Jump Game II даёт наименьшее число клипов.
Каждый кран покрывает отрезок от i минус радиус до i плюс радиус, так что запиши самую дальнюю точку для каждого левого конца и считай прыжки как в Jump Game II.