[Dynamic Programming] 계단 오르기 - 초급

→

 

📋 LeetCode 70번

Climbing Stairs - LeetCode

 

올라가야 하는 계단의 수: n

n으로 올라가기 위한 경우의 수는 n-1에서 1칸 or n-2에서 2칸 올라 가는 두 가지 방법이 있다.

-> 피보나치 수와 같다!

 

👩🏻‍💻 내 풀이

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

 

 

 

📋 LeetCode 746번

Min Cost Climbing Stairs - LeetCode

올라가는데 인덱스 마다 각각 arr = [ 1, 2, 4, 6, 2, 4, 6, 1 ]의 비용이 드는 계단이 있다.

계단은 1칸 or 2칸 올라갈 수 있다.

 

F(0)으로 올라가는데 드는 비용은 0

F(1)으로 올라가는데 드는 비용도 0

 

F(2)으로 올라가는 경우의 수는 F(0)에서 2칸 올라가기 or F(1)에서 1칸 올라가기

→ arr[0],arr[1]의 최솟값 : min(F(0)+1,F(1)+2) = 1

 

F(3)으로 올라가는 경우의 수는 F(1)에서 2칸 올라가기 or F(2)에서 1칸 올라가기

→ arr[1], arr[2]의 최솟값 : min(F(1)+arr[1], F(2)+arr[2]) = min(0+2, 1+4) = 2

.

.

 

$$F(n) = min( F(n-2) + cost(n-2) , F(n-1) + cost(n-1)  )$$

 

시간 복잡도 : O(n)

공간 복잡도 : O(n) → 사실상 저장하는데 필요한 공간은 2칸이므로 O(1)로 줄일 수 있다.

 

👩🏻‍💻 내 풀이

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        arr=[0,0]
        for i in range(2,len(cost)+1):
            # print(f'{i}번째 {arr[i-2]+cost[i-2]} {arr[i-1]+cost[i-1]}')
            arr.append(min(arr[i-2]+cost[i-2], arr[i-1]+cost[i-1]))
        return arr[-1]