[LeetCode] 746. Min Cost Climbing Stairs - 파이썬(Python)

문제 링크 : https://leetcode.com/problems/min-cost-climbing-stairs/

Min Cost Climbing Stairs - LeetCode

유형 : 동적 계획법(Dynamic Programming)

문제 설명

계단을 밟는 비용이 담긴 정수 배열 cost가 주어질 때, 계단 꼭대기에 도달하기 위한 최소 비용을 return 하는 문제이다. 이때, 비용을 지불하면 계단을 1칸 또는 2칸을 오를 수 있고, 0번째 혹은 1번째 계단에서 시작할 수 있다.

Example 1)
Input: cost = [10,15,20]
Output: 15

Example 2)
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6

제한사항

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

문제 풀이

성공 코드

from typing import List

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        total_count = len(cost)
        min_cost = [0] * (total_count+1)
        
        for i in range(2, total_count + 1):
            one_step = min_cost[i-1] + cost[i-1]
            two_step = min_cost[i-2] + cost[i-2]
            min_cost[i] = min(one_step, two_step)

        return min_cost[total_count]

시간 복잡도 : O(n)

공간 복잡도 : O(n)

기본적으로 Memoization 기법을 사용하면 O(n)의 공간복잡도가 필요하지만, 사실상 n-1과 n-2번째 계단의 최소 비용만으로 n번째 계단의 최소 비용을 구할 수 있으므로 시간 복잡도를 O(1)으로 줄일 수 있다.