[NeetCode/Python] Min Cost Climbing Stairs

문제 링크: https://neetcode.io/problems/min-cost-climbing-stairs

NeetCode

 

예전에 알고리즘 감을 살릴겸, 순차적으로 구하는 방법, 역순으로 구하는 방법 두 방법 모두를 사용해서 풀어보았다.

점점 이제 이지 난이도에서 벗어나야할텐데... 준비중이다!

 

 

[내 코드 1: 순차적 풀이]

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        result = [0 for i in range(len(cost))]

        # cost.length >= 2
        result[0], result[1] = cost[0], cost[1]
        for i in range(2, n):
            result[i] = min(result[i-1], result[i-2]) + cost[i]
        
        return min(result[n-1], result[n-2])

 

 

[내 코드 2: 역순 풀이]

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(len(cost)-3, -1, -1):
            cost[i] += min(cost[i + 1], cost[i + 2])
        
        return min(cost[0], cost[1])

 

시간 복잡도

두 풀이 모두 n이 cost 리스트의 길이일 때,

=> O(n)