Проблема
Вы поднимаетесь по лестнице. Чтобы добраться до вершины, требуется 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 или 2.
- В противном случае нам нужно будет зацикливаться, пока «i» не станет равным «n». На каждой итерации мы будем назначать memo[i] равным сумме двух предыдущих значений. Это позволит нам запомнить предыдущие значения, что снизит вычислительную мощность, необходимую для запуска функции.
- Как только цикл удовлетворяет условию завершения, все, что нам нужно сделать, это вернуть memo[n], чтобы получить ответ.