Учитывая лестницу с 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).
Вот и все. Комментарий ниже, если у вас есть лучшее решение.
Надеюсь, вам понравилось.
Спасибо
Вечнозеленое кодирование