Учитывая лестницу с n ступенями, найдите количество способов подняться по ней, если мы можем сделать либо 1 ступеньку, либо 2 ступени за раз.

steps = 1
--> expect 1 (as only one way to climb 1 step, which is to take 1 step)
steps = 2
--> expect 2 (as can either take 2 1-steps, or 1 2-step)
steps = 5
--> expect 8

Почему бы не взять ручку и бумагу и не попробовать.

Рассуждение

Когда мы записываем последовательность от небольшого количества шагов к большему количеству шагов и смотрим, есть ли какие-либо закономерности, мы понимаем, что количество способов подняться на n шагов = количеству способов подняться (n-1) шагов. (сделать 1 шаг в качестве последнего шага)+ количество способов подняться (n-2) шагов (сделать 2 шага в качестве последнего шага).

steps = 3
--> num ways(step = 3 - 1) + num ways(step = 3 - 2)
--> num ways(step = 2) + num ways(step = 1)
--> = 2 + 1
--> = 3
steps = 4
--> num ways (step = 4 - 1) + num ways (step = 4 - 2)
--> num ways (step = 3) + num ways (step = 2)
--> 3 + 2
--> 5
steps = 5
--> num ways (step = 5- 1) + num ways (step = 5- 2)
--> num ways (step = 4) + num ways (step = 3)
--> 5 + 3
--> 8

Мы видим, что это рекурсивная проблема, когда каждый вызов функции вызывает сам себя дважды.

Решение в коде

Используя рекурсию, мы пересчитываем результаты. Например, когда steps = 4, мы вызываем steps = 3 и steps = 2. Но steps = 3 снова вызовет steps = 2. Временная сложность составляет O (2 ^ n), а пространственная сложность также составляет O (2 ^ n).

Чтобы сделать программу более эффективной, мы можем хранить количество способов добраться до каждого шага в массиве. Таким образом, мы можем считывать значение в массиве без использования рекурсии и пересчета. В этом случае временная сложность равна O(n), а пространственная сложность также равна O(n).

Чтобы сделать программу еще более эффективной, мы можем просто использовать 3 переменные для хранения значений, необходимых на каждой итерации. Это еще больше снижает пространственную сложность до O (1).

Вот и все. Комментарий ниже, если у вас есть лучшее решение.

Надеюсь, вам понравилось.

Спасибо

Вечнозеленое кодирование