[알고리즘] LeetCode 746번 "Min Cost Climbing Stairs" (C/C++) - Don 임베디드

문제요약:

You are given an integer array cost[] where cost[i] is the cost of ith step on staircase.

Once you pay the cost, you can either climb one or two steps from there.

You can either start from the step[0] or step[1]

Return the minimum cost to reach the top of the floor.

 

제약:

2 <= cost.length <= 1000

0 <= cost[i] <= 999

 

예제 1 입력.	예제 1 출력.
[10,15,20]	15
예제 2 입력.	예제 2 출력.
[1,100,1,1,1,100,1,1,100,1]	6
예제 3 입력.	예제 3 출력.
[10,15]	10

 

정답코드:

class Solution {
public:
    // basic idea
    //             n   -> (X < Y) ? (X + cost[n]) : (Y + cost[n]); 
    //      n-1        -> min cost: X
    // n-2             -> min cost: Y
    
    int minCostClimbingStairs(vector<int>& cost) {
        int minCost1Step;
        int minCost2Step;
        int newMinCost;
        
        cost.push_back(0);
        
        minCost1Step = cost[1];
        minCost2Step = cost[0];
        
        for (int i = 2; i < cost.size(); i++)
        {
            newMinCost = (minCost1Step < minCost2Step) ? (minCost1Step + cost[i]) : (minCost2Step + cost[i]);
            minCost2Step = minCost1Step;
            minCost1Step = newMinCost;
        }
        
        return newMinCost;
    }
};

핵심 Idea:

Dynamic Programming.

If you know the min cost for step[n-2] and step[n-1] it is easy to compute mincost[n].

The final step has no cost, but you have to get there.

=> this is why I added the node with 0 cost at the end of the vector<int> cost.

 

원본 링크: https://leetcode.com/problems/min-cost-climbing-stairs/