Лестница (шаг 1 или 2)
Сколькими способами подняться по лестнице — это Фибоначчи в костюме задачи.
1function climbStairs(n: number): number {2 const ways = [1, 1]3 for (let i = 2; i <= n; i++) {4 ways[i] = ways[i - 1] + ways[i - 2]5 }6 return ways[n]7}Проблема
Сколькими способами подняться по лестнице — это Фибоначчи в костюме задачи.
Что вы видите
Ступеньки с накопленными способами: каждая цифра — сумма двух предыдущих.
Как это работает
На ступень i приходят только с i−1 и с i−2: ways[i] = ways[i−1] + ways[i−2]. Лестница превращает абстрактную рекурсию в осязаемую динамику — идеальная первая DP-задача.
Пошаговый разбор
- 01
База
Земля и первая ступень.
- 02
Шаг
Сумма двух предыдущих.
- 03
Ответ
Вершина лестницы.
Complexity и ограничения
Сложность см. в шапке страницы.
Edge cases
- Пустой вход
Корректная тривиальная обработка.
- Вырожденный случай
Минимум работы — сразу ответ.
Где встречается в реальности
Собеседования
Канонический вводный вопрос по динамике.
Автоматы
Счёт путей в конечных автоматах.
Планирование
Разбиение сроков на шаги.
Связанные алгоритмы
«Лестница, которая на самом деле Фибоначчи»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.