[1D DP][Easy] 746. Min Cost Climbing Stairs

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

 

정수배열 cost는 각 계단을 밟는 비용을 의미한다. 

한번에 계단은 하나 혹은 두개씩 밟을 수 있다.

시작은 0이나 1 위치에서 시작 할 수 있다.

이때, 최고 높은 계단에 도달하기 위한 최소 비용을 구하라. 

 

 

특정 위치에서 비용은 

cost[idx] + min(1단계, 2단계) 

일 것이다. 

 

위를 기준으로 코드를 만든다.

 

코드 

int minCostDP(vector<int>& vCache, int idx, vector<int>& cost)
{
    if(idx >= cost.size())
        return 0;

    if(vCache[idx] >= 0)
        return vCache[idx];

    vCache[idx] = cost[idx] + min(minCostDP(vCache, idx+1, cost), minCostDP(vCache, idx+2, cost));
    return vCache[idx];
}


int minCostClimbingStairs(vector<int>& cost) 
{
    vector<int> vCache;
    vCache.resize(cost.size(), -1);
    return min(minCostDP(vCache, 0, cost), minCostDP(vCache, 1, cost));
}

 

 

결과