[Python][LeetCode] Climbing Stairs(계단오르기)

https://leetcode.com/problems/climbing-stairs/description/

Climbing Stairs - LeetCode

문제설명:

정상에 도달하기 위해 n 계단을 올라가야 한다.

정상에 도달하기 위한 경로의 수

3일 때

1->1->1

1->2

2->1

 

피보나치 수열과 푸는 방법은 같지만 시간초과에 주의해야 한다.

 

class Solution:
    store = collections.defaultdict(int)

    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        if self.store[n]:
            return self.store[n]
        self.store[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
        return self.store[n]

 

컬렉션을 사용 딕셔너리 값에 n이 재귀를 돌때마다 값을 저장시켜줄 것이다.

처음 재귀가 돌때는 5,4는 0을 가지고 있다.

가장 밑에서부터 1과 2는 반환 그럼 3은 3 3이 반환되면 4로 올라갔을때 4는 5 마지막으로 다시 5로 올라가면 8 n이 5일때 8가지 방법이 나온다.