Climbing Stairs

Разбейте подъёмы на ступень n по их последнему шагу. При подъёме, заканчивающемся шагом на 1 ступень, перед ним находились на ступени n-1, и таких подъёмов ways(n-1). При подъёме, заканчивающемся шагом на 2 ступени, находились на ступени n-2, и таких подъёмов ways(n-2). Каждый подъём заканчивается одним из этих двух способов, и ни один не заканчивается обоими способами, поэтому ways(n) = ways(n-1) + ways(n-2).

Рекурсии нужны два базовых случая. На одну ступень есть один подъём, а на две ступени — два (1, 1 и 2). В обоих случаях ответ равен n, поэтому функция возвращает n при n ≤ 2, а в остальных случаях — сумму.

Ответ правильный, но объём вычислений стремительно растёт. Вызов climbStairs(5) дважды запрашивает ступень 3 и трижды ступень 2 — всего 9 вызовов, а количество вызовов растёт примерно так же, как сами ответы. При n = 45 функция делает 2269806339 вызовов, около 2.3 × 10^9, что намного превышает допустимое время выполнения. Глубина рекурсии составляет всего n уровней, поэтому стек занимает O(n) памяти.

Рекурсия медленная только потому, что она забывает. Каждый подсчёт зависит только от k, поэтому, узнав количество для шага k, ты уже знаешь его навсегда. Используй мемоизацию — массив с одной ячейкой на каждый шаг — и записывай туда количество при первом вычислении. При каждом последующем запросе того же шага значение считывается из ячейки, вместо того чтобы снова запускать рекурсию.

Теперь каждое количество для шагов от 3 до шага n вычисляется один раз, с одним сложением. Для n = 5 вызовы доходят до шага 2 один раз, затем ответы возвращаются обратно как 3, 5 и 8, а при повторном запросе шага 3 значение считывается из ячейки. Это время O(n) вместо миллиардов вызовов.

В мемоизации хранятся n + 1 чисел, а глубина рекурсии по-прежнему составляет n уровней, поэтому пространственная сложность — O(n). 0 в ячейке означает, что значение ещё неизвестно; это безопасно, потому что каждое реальное количество не меньше 1.

Разверните рекурсию. Вместо того чтобы начинать сверху и двигаться вниз, начните снизу и стройте решение вверх. Когда вы вычисляете количество способов для шага k, количества для k-1 и k-2 уже известны, и к более ранним значениям больше не обращаются. Поэтому вместо всего кэша достаточно двух переменных.

Пусть prev хранит количество способов для шага k-2, а curr — для шага k-1. Начните с prev = 1 и curr = 2 — это количества способов для шагов 1 и 2. На каждом шаге сложите их в next, а затем сдвиньте пару вперёд. Для n = 5 пара меняется с (1, 2) на (2, 3), (3, 5) и (5, 8), и curr = 8 — это ответ.

Цикл выполняется n-2 раз, каждый раз выполняя одно сложение, поэтому время работы — O(n), а используются три целых числа, то есть требуется O(1) памяти. Вычислите next, прежде чем перезаписать prev, иначе при сложении будет использовано неверное значение.