[leetcode] 계단 오르기

Climbing Stairs
링크텍스트
계단의 맨 위로 올라가기 위해 오를 수 있는 방법의 수를 세는 문제이다.
한번 계단을 오를 때마다 1칸 또는 2칸을 오를 수 있다.
예를 들어 n=3 이면, 3칸을 올라가기 위해 총 세 가지의 방법이 존재한다.
1. 1칸 + 1칸 + 1칸
2. 1칸 + 2칸
3. 2칸 + 1칸
-> 3가지 방법

동적 프로그래밍으로 풀 수 있다.

import collections

class Solution(object):
    def climbStairs(self, n):
        
        # 시간 초과 에러 방지를 위해 별도의 메모리 선언
        dp = collections.defaultdict(int)	
        
        def climbing(n):
            if n <= 3:  # n=3일때까지 정답은 n개이다.
                return n
            if dp[n]:   		# 값이 메모리에 존재한다면더이상 계산하지 말고 
                return dp[n]	# 그 값 반환
            
            dp[n] = climbing(n-1) + climbing(n-2)
            return dp[n]

        return climbing(n)