LeetCode 746 - Min Cost Climbing Stairs ( C++ )

 

문제 풀이

 

DP (Dynamic Programming) 문제이므로 기록해둔 과거 계산 값을 이용해서 현재 값을 계산해야 한다. 

 

i번째 계단까지 올라가는데 최소한의 cost를 기록하자.

 

i번째 계단을 올라갈때 계단을 한 칸 올라가거나, 두 칸 올라갈 수 있으므로, cost [i-1]와 cost [i-2] 중 작은 값을 cost [i]에 더해준다.

 

cost의 마지막 원소까지 계산하고, 뒤에서 첫번째 원소 값과 두 번째 원소 값 중 작은 값을 정답 값으로 반환한다.

 

 

 

+

 

dp를 기록할 새로운 배열을 만들 필요가 없으므로 주어진 cost 배열을 dp에 이용하여 메모리 사용량을 줄이자

 

코드

 

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        
        int len = cost.size();
       
        for (int i = 2 ; i < len ; i++) 
            cost[i] += min(cost[i-1], cost[i-2]);
        
        return min(cost[len-1], cost[len-2]);
    }
    
};

 

 

결과