[Leetcode] climbstairs (python, dp)

계단 오르기 문제 

메모이제이션으로 재귀로 풀어도 되고 반복문으로 풀어도 된다

1계단에 오르는 방법 1로 가는거 한 가지,

2 계단에 오르는 법은 1에서 1칸 가는 방법, 0에서 2칸 가는 방법 2가지로 초기화한다.

 

나머지만 현재 위치보다 1칸 아래에서 오는 방법과 2칸 아래에서 오는 방법을 더해주면 된다 

from collections import defaultdict
class Solution:
    def climbStairs(self, n: int) -> int:
        dp=defaultdict(int)
        
        dp[1]=1
        dp[2]=2
        for i in range(3,n+1):
            dp[i]=dp[i-1]+dp[i-2]
            
        return dp[n]