День 9: Задача «Подъем по лестнице».

Проблема:

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

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

Примечание: заданное n будет положительным целым числом.

Пример 1:

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

Пример 2:

Input: 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

Мое решение:

class Solution:
    def climbStairs(self, n: int) -> int:
        if(n<=2):
            return n
        else :
            one_step_back = 2
            two_steps_back = 1
            current_step = 0
            for i in range(3, n+1):
                current_step = one_step_back + two_steps_back
                two_steps_back = one_step_back
                one_step_back = current_step
        return current_step

Пояснение:

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

Первый шаг может быть достигнут только одним способом. Так же, мы можем подняться с пола на одну ступеньку.

На вторую ступень можно подняться 2-ступенчатым подъемом от пола или 1-ступенчатым подъемом от первой ступени. Число способов, которыми мы можем достичь первого шага, равно одному. Таким образом, мы можем достичь Шага 2 двумя способами.

За одно восхождение на Шаг-3 можно подняться либо за 2 шага из Шага-1, либо за один шаг из Шага-2. Но к Шагу 2 можно добраться двумя способами, а к Шагу 1 - одним. Это дает нам три способа достичь Шага-3, два - через Шаг-2 и один - через Шаг-1.

То же правило применяется к Шагу-4. За один подъем на Шаг-4 можно подняться либо за 2 шага из Шага-2, либо за один шаг из Шага-3. Но шага 3 можно достичь тремя способами, а шага 2 - двумя способами. Это дает нам пять способов достичь Шага-4, три - через Шаг-3 и два - через Шаг-2.

Итак, мы видим здесь закономерность. На любом шаге количество способов достичь шага - это сумма количества способов достичь предыдущего шага и количества способов достичь шага, предшествующего предыдущему шагу.

Так мы решаем проблему «Подъем по лестнице».

Если вы заинтересованы в решении других проблем, следуйте 60 дней программирования и присоединяйтесь ко мне в этом путешествии.

Если вы хотите, чтобы я решил и объяснил какие-либо проблемы, добавьте их в качестве комментариев вместе со ссылкой на описание проблемы.

Увидимся завтра!

Ваше здоровье!