[Algorithm] min-cost-climbing-stairs 문제

 

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

Min Cost Climbing Stairs - LeetCode

---

처음에 풀었을 때

- 매개변수로 주어지는 cost 배열을 이용 안 하고 dp 테이블을 따로 만듬 

- 시간복잡도 올라감 

class Solution(object):
    def minCostClimbingStairs(self, cost):
        cost.append(0)
        n = len(cost)
        d = cost # 이 부분에서 급 올라간듯
        for i in range(len(cost) - 3, -1, -1):
            d[i] = cost[i] + min(d[i + 1], d[i + 2])
        print(min(d[0],d[1]))
        return min(d[0], d[1])

 

---

시간복잡도 줄인 방향 풀이 

- dp 테이블 따로 선언 안 하고 cost 배열 그대로 이용함

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