[Python]파이썬 - 계단오르기 (DP: 메모이제이션 방식)

Python : 계단오르기 문제

Dynamic Programming(동적 계획법) 기반 메모이제이션 방식 사용

 

리트코드 문제 - https://leetcode.com/problems/climbing-stairs/

def climb_stairs(n):
    dp = collections.defaultdict(int)
    
    if n <= 2:
        return n
    
    if dp[n]:
        return dp[n]
    
    dp[n] = climb_stairs(n-1) + climb_stairs(n-2)
    # 예) n이 3이라면 n=2일때의 경우의 수 + n=1일때의 경우의 수를 합 
    return dp[n]

n=3
res = climb_stairs(n)
print(res)