[1D DP][Medium] 198. House Robber

https://leetcode.com/problems/house-robber/description/

 

정수 배열이 주어지고 이것은 각 집과 훔칠 수 있는 돈을 의미한다.

도둑은 인접한 집은 방문할 수 없다. 

모든 집을 털었을 때, 기대할 수 있는 최대 값을 찾아라.

 

아래 문제에 비유적 설명을 덧댄 문제.

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

 

인접해서 방문 할 수 없으므로, 

특정 위치에서 기대 할수 있는 최대 값은

nums[idx] + max(idx+1 이동, idx+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));
}

 

 

 

결과