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

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. 계단아래서부터 주어진 계단을 하나 혹은 두개씩 점프해서 올라갈 수 있다. 

 각 계단을 밟을시 비용이 cost vector가 주어질때, top 에 도달하기 위한 최소 비용을 구하라. 

 

Solution. 

  Dynamic Programming이 알고리즘에서 난해한 분야에 속하는 이유는 일반적으로 계산을 누적해서 해야 한다는데 있다. 

따라서 이것은 사람이 머릿속으로 되뇌이는 과정과 다소 차이가 있는 것이다. 

다시 말해서 이것을 잘 풀기위해서는 단계 기준으로 잘 정리해 놓을 필요가 있다는 것이다. 

 

각 계단 별로(모든 계단에 적용되는) 로직을 생각해 본다. 

 

어떤 계단이든, 다음 계단 혹은 다음 다음 계단만 밟을 수 있다. 

이 계단의 최소 비용은 (현재 비용) + (다음 밟을 계단 부터 꼭대기의 최소 비용) 으로 정해진다. 

이것은 모든 단계에서 같다. 

다만 다 올라가버리면, 더 갈 필요가 없으므로, 그때부터 비용은 0 이 된다. 

 

최대한 직관적이고 간결하게 알고리즘을 작성한다. 

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

    int cost1 = climb_helper(cost, idx + 1);
    int cost2 = climb_helper(cost, idx + 2);

    return cost[idx] + min(cost1, cost2);
}

int minCostClimbingStairs(vector<int>& cost) 
{
    return min(climb_helper(cost, 0), climb_helper(cost, 1)); 
}

 

기본 샘플은 통과 했으나 예상대로, TC 를 통과하지 못한다. 

 

 

다음으로 누적 재계산을 피하기 위해 캐시버퍼를 사용해 최적화 해 본다. 

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

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

    int cost1 = climb_helper(cache, cost, idx + 1);
    int cost2 = climb_helper(cache, cost, idx + 2);

    cache[idx] = cost[idx] + min(cost1, cost2);
    return cache[idx];
}

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

 

 

통과는 했지만, 더 최적화의 여지도 보인다. 

하지만 이를 위해 로직을 더 꼬으거나 trim 하기보다 문제 이해를 위해 이정도에서 정리한다.