Jump Game

Самая очевидная идея — разыграть всё на практике. Встаньте на индекс 0 и по очереди попробуйте каждую позицию приземления, до которой позволяет допрыгнуть. Повторите то же самое для каждой позиции приземления. Если какая-либо ветвь приводит к последнему индексу, ответ — true. Если каждая ветвь заканчивается тупиком, ответ — false.

В первом примере в индексе 0 находится 2, поэтому вы пробуете индекс 1 и индекс 2. В индексе 1 находится 0 — это тупик, поэтому вы возвращаетесь назад и пробуете индекс 2. В индексе 2 находится 3, и оттуда можно добраться до индекса 5, последнего индекса, поэтому поиск завершается ответом true.

Поиск корректен, потому что проверяет каждый маршрут. В этом и заключается его проблема: он не запоминает уже исследованные индексы, поэтому исследует один и тот же индекс снова для каждого ведущего к нему маршрута. Когда ответ — false, ему приходится исключить все маршруты. В [4, 3, 2, 1, 0, 5] из каждого индекса перед 0 можно добраться до 0, поэтому к нему ведут 8 разных маршрутов. Если таких индексов 30, маршрутов будет больше 500 миллионов, а самые большие тесты содержат 10,000 элементов. Такой длинный маршрут также может привести к переполнению стека вызовов в некоторых языках: Python по умолчанию останавливается после 1,000 вложенных вызовов.

В приведённом выше поиске снова и снова задаётся один и тот же вопрос: «может ли индекс j завершить путь?». Ответ для j никогда не меняется, поэтому вычисли его один раз и сохрани. Считай индекс хорошим, если из него можно добраться до последнего индекса. Последний индекс — хороший. Любой другой индекс i хороший, если хорош хотя бы один индекс, на который можно попасть из него: от i+1 до i+nums[i].

Каждый индекс зависит только от индексов справа от него, поэтому заполняй таблицу good справа налево. В первом примере индекс 5 — хороший. В индексе 4 хранится 0, поэтому он не хороший. Из индекса 3 можно попасть только в индекс 4: он не хороший. Из индекса 2 можно попасть в индексы 3, 4 и 5, а индекс 5 хороший, значит, индекс 2 тоже хороший. В индексе 1 хранится 0: он не хороший. Из индекса 0 можно попасть в индексы 1 и 2, а индекс 2 хороший, поэтому ответ — true.

Теперь решение для каждого индекса вычисляется один раз, но при этом всё ещё может потребоваться просмотреть до n ячеек. В [9998, 9997, …, 1, 0, 7] из каждого индекса можно добраться до 0, но нельзя пройти дальше, поэтому каждый индекс просматривает весь свой диапазон и не находит ничего хорошего. Для 10 000 элементов это около 5 × 10^7 проверок, и самые большие тесты устроены именно так. Объём работы растёт пропорционально квадрату длины, поэтому на таких тестах алгоритму не хватает времени.

Смотрите на индексы, до которых можно добраться, а не на маршруты. Из индекса i можно попасть на любой индекс от i+1 до i+nums[i], без пропусков. Поэтому, как только индекс i становится достижимым, достижим и каждый индекс вплоть до i+nums[i]. Начните только с индекса 0 и продолжайте добавлять такие отрезки. Каждый новый отрезок начинается внутри уже имеющегося блока, поэтому достижимые индексы всегда образуют один непрерывный блок, [0, farthest].

Именно поэтому достаточно одного числа. Проходите по i слева направо. Пока i ≤ farthest, индекс i достижим, поэтому расширяйте farthest до max(farthest, i+nums[i]). Если i когда-либо превысит farthest, ни один достижимый индекс не перепрыгнет до i. Блок не может вырасти через этот разрыв, поэтому ничто правее него недостижимо, включая последний индекс. Если проход дойдёт до конца без разрыва, последний индекс достижим.

Во втором примере farthest равен 0, затем становится равен 1 после индекса 0, а потом — 4 после индекса 1. В индексах 2, 3 и 4 находятся нули, поэтому значение остаётся равным 4. Индекс 5 находится за пределами 4, поэтому ответ — false. В первом примере индекс 2 увеличивает farthest до 5, и ни один индекс не оказывается за его пределами, поэтому ответ — true.

Почему безопасно хранить только максимальную дальность? Вы не выбираете конкретный прыжок заранее. Блок содержит каждый индекс, достижимый по любому маршруту, а каждая более короткая точка приземления находится внутри него. Если отбросить всё, кроме правой границы, никакая информация не теряется.