Выбор ответа Middle Жадные обновлено
Можно ли допрыгать до конца
Вопрос
nums[i] это максимальная длина прыжка из позиции i. Можно ли дойти до последнего индекса? Оптимальный подход?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Жадно держать самую дальнюю достижимую позицию, O(n). Достижимые позиции образуют префикс [0, far].
Варианты ответа
- Перебор всех путей прыжков рекурсией с возвратом
- Жадно держать самую дальнюю достижимую позицию, O(n)правильный ответ
- Динамика O(n²): для каждой позиции проверить все прошлые
- BFS по позициям обязателен, иначе пропустим путь
Разбор
Достижимые позиции образуют префикс [0, far]. Каждый i внутри него расширяет far до i + nums[i]. Если i > far, дальше не пройти. Один проход, O(1) памяти.
- Перебор экспоненциален.
- Динамика верна, но O(n²).
- BFS работает, но не нужен: достижимость это просто отрезок.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.