99클럽 코테 스터디 40일차 TIL + 리트코드 DP

 

주제 : 동적계획법

https://leetcode.com/problems/min-cost-climbing-stairs/

 

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0] * (n + 1) 

        for i in range(2, n + 1):
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        
        return dp[n]

 

dp[i]는 i번째 계단에 도달하는 최소 비용을 저장한다
dp[0]과 dp[1]은 0으로 초기화하고,

나머지 값을 순차적으로 계산하는 중

맨 마지막 dp[n]은? 결과값

시간 복잡도: O(n), 공간 복잡도 :  O(n)