55. Jump Game — разбор задачи

Условие задачи

Дано: непустой массив неотрицательных чисел nums; начинаем на позиции 0, а nums[i] задаёт максимальную длину прыжка из позиции i. Условие на LeetCode
Нужно: вернуть True, если можно добраться до последнего индекса, иначе False. Условие на LeetCode
Разрешено: прыгать вправо на расстояние меньше максимального, то есть из i можно выбрать любую следующую позицию от i + 1 до i + nums[i], не выходя за массив. Условие на LeetCode

Главное слово здесь: максимальная длина прыжка. Значение 3 не заставляет нас прыгать ровно на три клетки: можно прыгнуть на одну, две или три. Условие на LeetCode

Например, для nums = [2, 3, 1, 1, 4] ответ True: прыгаем с индекса 0 на индекс 1, а оттуда на последний индекс 4. Для nums = [3, 2, 1, 0, 4] ответ False: из первых трёх позиций дальше индекса 3 не прыгнуть, а на нём стоит ноль. Примеры на LeetCode

Ограничения: 1 <= len(nums) <= 10^4, 0 <= nums[i] <= 10^5. Массив из одного элемента разрешён: мы уже на финише, даже если этот элемент равен нулю. Условие на LeetCode

Основное решение: на каждой станции можно сменить коня

Представим массив как дорогу со станциями. На каждой станции стоит конь, которому хватит сил на nums[i] перегонов, а один перегон означает переход на следующую станцию.

Мы начинаем на первой станции и берём её коня. Добравшись до любой следующей станции, можем сменить коня или продолжить ехать на прежнем.

В обсуждениях LeetCode есть похожий рефрейм на бензин: его описывает RobertBanu в комментариях к официальному editorial, а Francisco Restrepo использует в популярном Python-решении. Там важно не складывать бензин, а выбирать больший из прежнего и нового запасов; здесь будем объяснять ту же идею через смену коней.

Как выбираем коня

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

Получаем stamina = max(stamina, num). Силы двух коней не складываются: дальше едем на одном из них, а не получаем нового коня с суммарной выносливостью.

Например, у нашего коня осталось сил на 2 перегона, а местный может пройти 5. Пересаживаемся на местного: теперь доступно 5 перегонов, не 7.

А если наш конь ещё может пройти 4 перегона, а местный только 1, менять коня незачем. Оставляем прежнего и едем дальше.

Почему это всё ещё задача про прыжки

Представим, что на индексе 0 стоит число 4. В исходной задаче это означает, что мы можем выбрать любую из позиций 1, 2, 3, 4.

В модели с конями на первой станции берём коня с выносливостью 4. После движения на индекс 1 остаётся 3, на индекс 2 остаётся 2: всё это просто способы описать ту же возможность добраться до индекса 4.

Если по дороге встретили коня, который позволяет добраться ещё дальше, пересаживаемся на него. Например, на индексе 2 стоит число 5: местному коню хватит сил до 2 + 5 = 7, и прежняя граница 4 больше не нужна.

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

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

Алгоритм по шагам

Начинаем со stamina = 0: мы на первой станции, своего коня ещё нет.
Перебираем все станции, включая первую: for num in nums.
Если на входе в итерацию stamina < 0, до текущей станции добраться не удалось: возвращаем False.
Выбираем коня с большей оставшейся выносливостью: stamina = max(stamina, num).
Вычитаем стоимость следующего перегона: stamina -= 1.
Если обработали все станции, возвращаем True: последняя станция достигнута.

На входе в итерацию stamina означает остаток сил после предыдущего перегона. Поэтому ноль допустим: мы приехали с последними силами и можем сменить коня; отрицательное значение означает, что предыдущий перегон был невозможен.

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

После последней станции тоже вычитаем единицу, чтобы тело цикла оставалось одинаковым. Но следующей станции нет, поэтому итоговые 0 или -1 не мешают ответу True: финиш уже достигнут.

Трассировка успешного примера

Возьмём nums = [2, 3, 1, 1, 4]. На каждой итерации сначала проверяем остаток, потом выбираем коня и вычитаем единицу за следующий перегон.

Станция	num	stamina на входе	После выбора коня	После вычитания единицы
0	2	0	`max(0, 2) = 2`	1
1	3	1	`max(1, 3) = 3`	2
2	1	2	`max(2, 1) = 2`	1
3	1	1	`max(1, 1) = 1`	0
4	4	0	`max(0, 4) = 4`	3

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

Трассировка неудачного примера

Теперь nums = [3, 2, 1, 0, 4]. На последней станции есть конь с выносливостью 4, но сначала нужно до неё добраться.

Станция	num	stamina на входе	После выбора коня	После вычитания единицы
0	3	0	`max(0, 3) = 3`	2
1	2	2	`max(2, 2) = 2`	1
2	1	1	`max(1, 1) = 1`	0
3	0	0	`max(0, 0) = 0`	-1
4	4	-1	Не выбираем коня: станция недостижима	Возвращаем `False`

На индекс 3 ещё добрались, а уехать с него уже не можем. Нельзя сначала пересесть на коня со станции 4, а потом проверить, хватало ли нам сил доехать до неё.

Код на Python

from typing import List


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        stamina = 0

        for num in nums:
            # До текущей станции нужно сначала добраться
            if stamina < 0:
                return False

            # Оставляем своего коня или пересаживаемся на более сильного
            stamina = max(stamina, num)
            stamina -= 1

        return True

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

Почему достаточно хранить силы одного коня

Допустим, на текущей станции один конь может пройти ещё 2 перегона, а другой 5. Всё, что доступно первому коню, доступно и второму: доехать на одну или две станции мы по-прежнему можем.

Менее выносливый конь не открывает никаких дополнительных вариантов. Значит, его можно забыть и оставить только более выносливого.

На следующей станции есть ровно два кандидата: наш конь с оставшимися после перегона силами и местный конь с выносливостью nums[i]. Мы сравниваем их и снова оставляем максимум, ничего полезного не теряя.

Если у лучшего коня перед перегоном нет сил, ни одна из ранее найденных возможностей не покрывает следующую клетку. В коде после вычитания получится -1, и на следующей итерации мы вернём False, не используя коня с недостижимой станции.

Если же обработали последнюю станцию, она была достижима: иначе проверка на входе уже вернула бы False. Значение после последнего вычитания на этот факт не влияет.

Сложность

Время: O(N), где N = len(nums): посещаем каждую клетку не больше одного раза, внутри цикла только проверка, вычитание и максимум.
Дополнительная память: O(1): храним выносливость stamina и текущее число num, не создаём массив состояний и не меняем nums.

Классическое решение справа налево: двигаем цель

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

Идея

Сначала цель goal стоит на последнем индексе. Из этой клетки до финиша уже добрались: прыгать не нужно.

Идём справа налево. Если из текущей позиции i можно прыгнуть на goal, то теперь достаточно добраться до i: от неё уже известен путь до финиша.

Проверка получается простой:

i + nums[i] >= goal

Если условие выполнено, переносим цель: goal = i. В конце остаётся проверить, дошла ли цель до индекса 0, на котором мы стартуем.

Здесь >=, а не ==: если максимальный прыжок проходит дальше цели, можно выбрать более короткий прыжок и приземлиться ровно на ней. Мы не прыгаем назад и не требуем перелететь за массив.

Трассировка с клетками, которые приходится пропустить

Возьмём nums = [2, 4, 2, 1, 0, 2, 0]. Сначала goal = 6; будем записывать его значение до и после проверки.

i	nums[i]	goal до проверки	i + nums[i]	Можно попасть на goal?	goal после проверки
5	2	6	7	Да	5
4	0	5	4	Нет	5
3	1	5	4	Нет	5
2	2	5	4	Нет	5
1	4	5	5	Да	1
0	2	1	2	Да	0

Получили goal == 0, значит, ответ True. Один подходящий маршрут: 0 → 1 → 5 → 6; клетки 2, 3, 4 нам не понадобились.

Код на Python

from typing import List


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1

        for i in range(len(nums) - 2, -1, -1):
            # До i теперь достаточно добраться вместо прежней цели
            if i + nums[i] >= goal:
                goal = i

        return goal == 0

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

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

А если до goal не дотягиваемся, то до остальных подходящих позиций справа тоже не дотянемся: они ещё дальше. Поэтому проверять их по отдельности не нужно.

Подходящие позиции не обязаны образовывать сплошной отрезок. В примере выше из индексов 2, 3, 4 финиш недостижим, но достаточно хранить ближайшую подходящую позицию 5.

Это тоже O(N) времени и O(1) дополнительной памяти. В отличие от основного решения, этот код всегда делает полный проход справа налево, даже если у самого начала массива стоит непреодолимое препятствие.

Классическое решение слева направо: самая дальняя позиция

Вместо оставшейся выносливости коня можно хранить абсолютную границу достижимости: farthest, самый дальний индекс, до которого позволяют добраться уже обработанные достижимые клетки. Так устроены C++-решение Alexander Belyaev и первый вариант в подборке Stefan Pochmann.

Сначала farthest = 0: на стартовой позиции мы уже стоим. Для каждой клетки i сначала проверяем, что она достижима, а потом пробуем расширить границу значением i + nums[i].

from typing import List


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0

        for i, jump in enumerate(nums):
            # Недостижимая клетка не может расширить нашу границу
            if i > farthest:
                return False

            farthest = max(farthest, i + jump)
            if farthest >= len(nums) - 1:
                return True

        return True

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

Поэтому достижимая область от старта не имеет дыр. Если текущий индекс i уже правее farthest, никакая клетка ещё правее не поможет: до неё тоже нельзя добраться.

Это то же решение, что и смена коней

Сразу после выбора коня на станции i, до вычитания единицы, выполняется stamina = farthest - i. Выносливость коня измеряет остаток пути от текущей станции, а farthest хранит конец этого пути в абсолютных индексах.

После вычитания получаем stamina = farthest - (i + 1): заранее учли расстояние до следующей станции. Если оно отрицательное, следующая станция правее доступной границы.

Местный конь с выносливостью nums[i] соответствует новой границе i + nums[i]: выбирая более выносливого коня, мы выбираем и более дальнюю границу. Так два алгоритма хранят одну информацию, но в разных координатах.

Обе записи работают за O(N) времени и O(1) памяти. В варианте с farthest удобно сразу вернуть True, как только граница покрыла последний индекс.

Краевые случаи и частые ошибки

Один элемент: [0] даёт True, потому что мы уже на последнем индексе; силы для следующего перегона не требуются.
Нельзя выехать со старта: [0, 1] даёт False; до коня на второй станции не добраться.
Доехали с последними силами и сменили коня: [1, 2, 0, 0] даёт True; на индекс 1 приезжаем с нулевой оставшейся выносливостью, берём местного коня с 2 и добираемся до конца.
Ноль по дороге можно перепрыгнуть: [2, 0, 0] даёт True; с первой клетки сразу доступна последняя.
Финиш может содержать ноль: [1, 0] даёт True; уезжать с последней клетки не нужно.
Всегда максимальный прыжок не подходит: для [2, 3, 0, 0, 0] прыжок 0 → 2 застревает, но маршрут 0 → 1 → 4 существует.
Нельзя складывать силы коней: ошибочная версия с суммой может пропустить [2, 1, 0, 0], хотя из первых двух клеток дальше индекса 2 не добраться.
Сначала достижимость, потом новая возможность: [0, 100] даёт False; нельзя использовать большое число из клетки, до которой не дошли.
Не проверяем остаток после цикла: на [0] или [1, 0] итоговая stamina равна -1, но ответ True: мы уже на последней станции, а ехать дальше не требуется.

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

Обзор дополнительных подходов

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

Полный перебор и мемоизация

Самый прямой подход: из каждой клетки попробовать все разрешённые прыжки. Если хотя бы один ведёт к финишу, возвращаем True; если все варианты провалились, возвращаем False.

Проблема в том, что в одну и ту же клетку можно попасть разными путями, после чего мы снова перебираем одинаковое продолжение. В худшем случае это O(2^N) времени и O(N) памяти на стек рекурсии, как разобрано в editorial.

Добавим запоминание ответа для каждой клетки. Каждое состояние теперь вычисляется один раз, но из него всё ещё может понадобиться проверить O(N) следующих клеток: получаем O(N^2) времени и O(N) памяти, включая кеш и стек, как в подходе с мемоизацией.

from functools import cache
from typing import List


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        @cache
        def can_finish(i: int) -> bool:
            if i == len(nums) - 1:
                return True

            end = min(i + nums[i], len(nums) - 1)
            for j in range(i + 1, end + 1):
                if can_finish(j):
                    return True

            return False

        return can_finish(0)

Этот код удобен для объяснения перебора: если убрать @cache, получится обычная рекурсия без запоминания. Но для больших входов на Python он не подходит как основной вариант: квадратичный перебор дорогой, а цепочка вызовов может упереться в лимит рекурсии.

DP справа налево и его сжатие до goal

Пусть good[i] означает, что из позиции i можно добраться до финиша. Тогда последняя клетка хорошая, а каждая предыдущая хороша, если из неё можно прыгнуть хотя бы в одну хорошую клетку справа; это состояние используется в официальном editorial.

Прыгаем только вправо, поэтому значения справа можно заранее посчитать. Получается DP без рекурсии:

from typing import List


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        good = [False] * n
        good[-1] = True

        for i in range(n - 2, -1, -1):
            end = min(i + nums[i], n - 1)
            for j in range(i + 1, end + 1):
                if good[j]:
                    good[i] = True
                    break

        return good[0]

Здесь O(N^2) времени и O(N) дополнительной памяти: для каждой клетки просматриваем возможные места приземления справа. Но нам не нужен весь массив good: достаточно знать самую левую хорошую клетку.

Если до неё дотягиваемся, ответ для текущей клетки True. Если нет, остальные хорошие клетки ещё дальше и не помогут; так внутренний цикл и массив good заменяются одной переменной goal.

Это полезный взгляд на обратное жадное решение: мы не угадали короткую формулу, а нашли в DP информацию, которой достаточно для следующего шага. Время сократилось до O(N), а память до O(1).

Вариант с явной проверкой перед перегоном

Наше основное решение обрабатывает все станции, а невозможный перегон отмечает отрицательной выносливостью; так же устроен цикл в решении Francisco Restrepo. Выбор коня и вычитание можно объединить в одну строку: stamina = max(stamina, num) - 1.

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

from typing import List


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        stamina = nums[0]

        for i in range(1, len(nums)):
            if stamina == 0:
                return False

            stamina -= 1
            stamina = max(stamina, nums[i])

        return True

В этой версии stamina на входе в итерацию означает силы перед перегоном с предыдущей станции. Поэтому проверяем stamina == 0, затем едем и только после приезда выбираем коня.

В основном решении проверка относится уже к прибытию на текущую станцию, поэтому там проверяем stamina < 0. Разница только в порядке действий и смысле состояния: обе записи работают за O(N) времени и O(1) памяти.

Обратный проход через расстояние до цели

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

from typing import List


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        need = 0

        for i in range(len(nums) - 2, -1, -1):
            need += 1
            if nums[i] >= need:
                need = 0

        return need == 0

Если после обработки первого индекса need == 0, стартовая клетка хорошая. Получается тот же обратный алгоритм за O(N) времени и O(1) памяти, только вместо координаты цели храним расстояние до неё.

BFS по диапазонам и функциональная запись

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

Если обрабатывать только новые индексы, каждый индекс просматривается один раз. Получается линейный проход с постоянной памятью; для проверки достижимости обычный farthest проще, а слои становятся полезны, когда нужно считать число прыжков.

В подборке Stefan Pochmann есть и однострочник через reduce. Это компактная запись прямого прохода, не новый алгоритм; исходный синтаксис рассчитан на Python 2, а явный цикл на современном Python легче читать и позволяет немедленно остановиться.

Вывод

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

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

Все три основных варианта дают O(N) времени и O(1) дополнительной памяти. Ключевое наблюдение одно: максимальная длина прыжка разрешает и все более короткие прыжки, поэтому не нужно отдельно хранить каждую доступную возможность.

🐆