[LeetCode] 70. Climbing Stairs

💡 문제

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?

ex)

💡 풀이

1️⃣ Recursive → Top-down

• i = 현재 위치, n = 목적지
• 현재 위치에서 다음 계단을 가는데에는 두 가지 방법이 있다.
  • 한 칸 오르기: i+1
  • 두 칸 오르기: i+2

    climb_stairs(i, n) = climb_stairs(i+1, n) + climb_stairs(i+2, n)
    i: 현재 위치, n: 목적지

def climb_stairs(i, n):
        if i>n:
            return 0
        if i==n:
            return 1
        
        return climb_stairs(i+1,n) + climb_stairs(i+2,n)

class Solution:       
    def climbStairs(self, n: int) -> int:
        return climb_stairs(0,n)

→ O(2^n)

이렇게 할 경우, 노드를 방문할 때 마다 매번 계산을 해줘야 하기 때문에 시간 초과가 난다. 중복되는 계산을 방지하기 위해, 이전 계산값을 저장했다가 해당 값이 필요할 때 꺼내쓰는 Memoization 방식을 통해 시간복잡도를 낮춰준다.

2️⃣ Recursive with Memoization → Top-down

• 이전 값들을 저장 할 memo 리스트를 생성한다.
• climb_stairs 함수를 호출할 때 0으로 채운 memo 리스트를 함께 전달한다.
• memo 리스트에 저장된 값이 있는 경우 해당 값을 불러온다.

def climb_stairs(i, n, memo):
    if i>n:
        return 0
    if i==n:
        return 1
    
    if memo[i]>0:
        return memo[i]
    
    memo[i] = climb_stairs(i+1,n,memo) + climb_stairs(i+2,n,memo)
    
    return memo[i]

class Solution:       
    def climbStairs(self, n: int) -> int:
        memo=[0]*(n+1)
        return climb_stairs(0, n, memo)

→ O(n)

3️⃣ DP → Bottom-up

• 재귀적으로 생각해보면 n번째 계단에 오르는 방법은 두 가지가 있다.
  - n-1번째 계단에서 한 칸 올라가는 방법
  - n-2번째 계단에서 두 칸 올라가는 방법
  
• 이를 점화식으로 세우면,

    dp[n] = dp[n-1]+dp[n-2]
    

• 0번째 계단과 1번째 계단에 오르는 방법은 각각 한 가지 이므로 dp 리스트를 [1, 1]로 초기화 해준다.

class Solution:       
    def climbStairs(self, n: int) -> int:
        dp=[1,1]
        
        for i in range(2, n+1):
            dp.append(dp[i-1] + dp[i-2])
            
        return dp[n]

→ O(n)

• 개인적으로 DP로 푼 방식이 가장 깔끔하고 직관적이다.