День 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 дней программирования и присоединяйтесь ко мне в этом путешествии.
Если вы хотите, чтобы я решил и объяснил какие-либо проблемы, добавьте их в качестве комментариев вместе со ссылкой на описание проблемы.
Увидимся завтра!
Ваше здоровье!