[leetcode] min cost climbing stairs - Python

문제링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제풀이

 

이번문제는 주어진 cost를 단계를 밟고 올라가 ( 1step or 2step )

정상으로 가는 최소의 비용을 구하는 것입니다.

이때 cost의 마지막 또는 마지막 전 index까지만 가면 됩니다.( 2칸 step으로 정상으로 가면되기 때문에)

DP를 이용해서 문제를 접근하였습니다.

memo로 해당 step에 대한 값을 적어놓고 해당 index가 왔을때 index-1 , index-2값을 비교하여 최소의 값으로 memo에 해싱해주었습니다.

 

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 최소의 비용으로 정상으로 가는 비용
        # 종료 조건 정상 n-1 or n-2

        memo = {}
        # 0,1 초기값 설정
        memo[0] = cost[0]
        memo[1] = cost[1]
        
        for i in range(2,len(cost)):
            memo[i] = min(memo[i-1] + cost[i], memo[i-2] + cost[i])
        
        goal = len(cost) -1

        return min(memo[goal], memo[goal-1])