[LeetCode] Climbing Stairs

난이도: EASY

문제 설명:
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

문제를 해결한 방법

---

Bottom-Up 접근

def climbStairs(self, n: int) -> int:
        # First Solution : Bottom-Up Approach
        if n <= 3:
            return n
        arr = [0] * (n+1)
        arr[1] = 1
        arr[2] = 2
        for i in range(3, n+1):
            arr[i] = arr[i-1] + arr[i-2]
        return arr[n]

Top-Down 접근

def climbStairs(self, n: int) -> int:
        def dp(n: int) -> int:
            if n <= 3:
                return n
            if n in memo:
                return memo[n]
            memo[n] = dp(n-1) + dp(n-2)
            return memo[n]
        memo={}
        return dp(n)