[c++/LeetCode-DP] 746. Min Cost Climbing Stairs

 

난이도: Easy

키워드: DP

 

 

 

 

📍 문제

정수 배열 cost가 주어지며, cost[i]는 계단의 i번째 단계의 비용입니다. 비용을 지불하면 1개 또는 2개의 단계를 오를 수 있습니다.
인덱스 0 또는 인덱스 1의 단계에서 시작할 수 있습니다.
최상위 층에 도달하기 위한 최소 비용을 반환하세요.

 

 

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

 

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

 

문제 원문: https://leetcode.com/problems/min-cost-climbing-stairs/description/

 

📍 문제 풀이

 

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {

        const int N = cost.size();
        vector<int> a(N+1, 0);
        
        if(N <= 1) return 0;
        a[0] = 0;
        a[1] = 0;

        for(int n=2; n <= N; ++n){
            a[n] = min(a[n-1] + cost[n-1], a[n-2] + cost[n-2]);
        }

        return a[N];
        
    }
};