Объясни жадное решение и его корректность
Вопрос
На примере задачи «можно ли допрыгать до конца массива» объясни жадное решение, его сложность и почему оно корректно.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Формулирует инвариант: достижимые позиции это отрезок [0, far]
Обновляет far = max(far, i + nums[i])
Останавливается, если i > far
O(n) времени, O(1) памяти
Обосновывает, а не говорит «работает на примерах»
Что могут спросить следом
- Как найти минимальное число прыжков?
- Чем решение динамикой хуже?
- Приведи задачу, где жадность ломается.
Разбор
Заметим, что если позиция j достижима, то достижимы и все позиции левее неё: до них можно допрыгнуть с того же пути, сделав прыжок короче. Значит, множество достижимых позиций это отрезок от 0 до far. Иду слева направо, и для каждого i внутри отрезка расширяю far до i + nums[i]. Если i оказался больше far, в эту точку не попасть, и дальше тоже, возвращаю false. Если far дошёл до последнего индекса, true. Один проход, O(n) времени и O(1) памяти. Динамика «dp[i] = достижима ли i» тоже верна, но O(n²). Для минимального числа прыжков та же идея превращается в BFS по уровням-отрезкам, тоже O(n).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.