Восхождение по лестнице

Вы поднимаетесь по лестнице. Требуется n шагов, чтобы добраться до вершины.

Каждый раз вы можете подняться на 1 или 2 ступеньки. Сколько существует различных способов чтобы подняться на вершину?

Пример №1

Ввод: n = 2
Вывод: 2
Объяснение: Здесь 2 способа подняться на вершину.
1. 1 шаг + 1 шаг
2. 2 шага

Пример №2

Ввод: n = 3
Вывод: 3
Объяснение: Здесь 3 способа подняться на вершину.
1. 1 шаг  + 1 шаг + 1 шаг
2. 2 шага + 1 шаг
3. 1 шаг  + 2 шага

Пример №3

Ввод: n = 4
Вывод: 5
Объяснение: Здесь 5 способов подняться на вершину.
1. 1 шаг  + 1 шаг  + 1 шаг + 1 шаг
2. 2 шага + 1 шаг  + 1 шаг
3. 1 шаг  + 2 шага + 1 шаг
4. 1 шаг  + 1 шаг  + 2 шага
5. 2 шага + 2 шага

Решение

Для решения задачи можно вспомнить числа Фибоначчи. Если применять последовательность к задаче, то количество способов забраться на n ступенек равно сумме способов для двух предыдущих.

Обратимся к примеру №3, чтобы лучше понять как это работает. Для поднятия с 3 на 4 ступень можно сделать только один шаг, т.е. взять все варианты для 3-й ступени и добавить к ним +1 шаг. Можете проверить, первые три шага в примере №2 и №3 имеют одинаковую последовательность, только в третьем добавился еще один шаг.

Такой же алгоритм применяем и для поднятия сразу на две ступени. Берем все варианты для 2-й ступени и добавляем +2 шага. Добавлять два раза +1 не надо, т.к. мы учли эту последовательность, когда добавляли +1 к 3-й ступени.

1. Вынесем ступени меньше 3 в отдельные проверки, чтобы не усложнять основной цикл.
2. Объявляем переменные, которые будут хранить количество комбинаций для шагов: oneStepBefore - кол-во комбинаций для предыдущей (n-1) ступени. twoStepsBefore - кол-во комбинаций для ступени перед предыдущей (n-2). allWays - кол-во комбинаций для текущей ступени (n).
3. В цикле применяем логику, которую я описал в начале раздела. Сначала вычисляем комбинации для текущей ступени, а потом сдвигаем oneStepBefore и twoStepsBefore на 1 ступень выше.

Код решения в виде текста

/**
 * @param {number} n
 * @return {number}
 */
const climbStairs = (n) => {
  // Базовые случаи
  if (n <= 0) {
    return 0
  }

  if (n == 1) {
    return 1
  }

  if (n == 2) {
    return 2
  }

  let oneStepBefore = 2;
  let twoStepsBefore = 1;
  let allWays = 0;

  for (let i = 2; i < n; i++) {
    allWays = oneStepBefore + twoStepsBefore;
    twoStepsBefore = oneStepBefore;
    oneStepBefore = allWays;
  }
  return allWays;
};