Проблема

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

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

Пример 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Пример 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Ограничения:

  • 1 <= n <= 45

Решение

Сначала я попытался решить это рекурсивно, но превысил ограничение по времени на больших входных данных, таких как 38. Оказывается, что использование того же подхода, что и задача Фибоначчи, является лучшим вариантом.

Расширение за пределы первых двух примеров позволяет выявить закономерность.

Ввод 4 дает результат 5

Ввод 5 дает результат 8

Ввод 6 дает результат 13

Ввод 7 дает результат 21

Я мог бы продолжать, но шаблон таков, что текущий индекс равен индексу двух предыдущих значений в массиве.

  1. Создайте памятку массива и загрузите в нее три начальных значения. Это будет охватывать сценарии, в которых вход равен 1 или 2.
  2. В противном случае нам нужно будет зацикливаться, пока «i» не станет равным «n». На каждой итерации мы будем назначать memo[i] равным сумме двух предыдущих значений. Это позволит нам запомнить предыдущие значения, что снизит вычислительную мощность, необходимую для запуска функции.
  3. Как только цикл удовлетворяет условию завершения, все, что нам нужно сделать, это вернуть memo[n], чтобы получить ответ.