70. Climbing Stairs

n개의 계단을 오른다.

한번에 1또는 2의 숫자만큼 계단을 오를 수 있다.

몇가지 경우의 수가 나오는가?

 

solution 1.

1은 1가지 경우의 수, 2는 2가지 경우의 수가 나온다는 것을 안다.

1: (1), 2 : (1,1), (2)

이를 이용하여 재귀 함수를 만든다.

 

class Solution:
    cnt = collections.defaultdict(int)
    def climbStairs(self, n: int) -> int:

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

타임아웃이 걸린다.

 

solution 2.

메모제이션을 활용하여 값을 저장해놓는다.

class Solution:
    cnt = collections.defaultdict(int)
    def climbStairs(self, n: int) -> int:

        if n == 1:
            return 1
        if n == 2:
            return 2
        if self.cnt[n]:
            return self.cnt[n]

        self.cnt[n] = self.climbStairs(n-1) + self.climbStairs(n-2)

        return self.cnt[n]

똑같이 타임아웃이 발생했으나, self.cnt[n]이 존재할 경우 리턴하는 코드를 넣어서 해결했다.