Выбор ответа Junior Динамическое программирование спрашивают часто обновлено
Лестница
Вопрос
Можно шагать на 1 или 2 ступеньки. Сколько способов подняться на n ступенек и какая оптимальная сложность?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: ways(n) = ways(n-1) + ways(n-2), O(n) и O(1) памяти. Последний шаг либо на 1, либо на 2 ступеньки: способы складываются.
Варианты ответа
ways(n) = ways(n-1) + ways(n-2), O(n) и O(1) памятиправильный ответ- 2ⁿ способов: на каждой ступеньке выбор из двух, O(2ⁿ)
- n способов: старт с каждой ступеньки даёт один путь, O(n)
n!способов: все порядки шагов различны, O(n!) перебором
Разбор
Последний шаг либо на 1, либо на 2 ступеньки: способы складываются. Это числа Фибоначчи. Храним только два предыдущих значения: O(n) и O(1).
- 2ⁿ это число всех бинарных последовательностей, многие из них не дают ровно n ступенек.
- n и n! не совпадают с подсчётом даже для n = 3 (ответ 3).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Предыдущий вопрос
Торговля акцией с комиссией и днём перерыва
Следующий вопрос
Инициализация в размене монет