[코테] 리트코드 다이나믹 프로그래밍 70. Climbing Stairs

70. Climbing Stairs

문제 링크

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

문제 설명

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

제한 사항

• 1 <= n <= 45

입출력 예 #1

1. Input : n = 2
2. Output : 2
3. Explanation : There are two ways to climb to the top. 1) 1 step + 1 step 2) 2 steps

입출력 예 #2

1. Input : n = 3
2. Output : 3
3. Explanation : There are three ways to climb to the top. 1) 1 step + 1 step + 1 step 2) 1 step + 2 steps 3) 2 steps + 1 step

문제 풀이

1. 재귀 구조 브루트 포스 (시간초과)
2. 메모이제이션을 활용한 재귀

class Solution:
    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)

class Solution:
    dp = collections.defaultdict(int)

    def climbStairs(self, n: int) -> int:
        if n <= 2 :
            return n
        
        if self.dp[n]:
            return self.dp[n]
        self.dp[n] = self.climbStairs(n - 1) + self.climbStairs(n - 2)
        return self.dp[n]