746. Min Cost Climbing Stairs

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

Min Cost Climbing Stairs - LeetCode

1,2 스탭을 움직일 수 있는데 가장 최소의 비용으로 계단을 올라가는 방법을 찾는 문제

DP 응용 문제이고 현재 위치에서 작은 값을 적산하여 출력한다.

 

D 풀이

현재 위치 = 최소값(현재 위치 - 2, 현재 위치 - 1)

시작점은 0, 1 둘 중에 하나를 선택

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        
        const int size = cost.size();
        for (int i = 2; i < size; i++) {
            cost[i] = cost[i] + min(cost[i - 2], cost[i - 1]);
        }

        return min(cost[size - 2], cost[size - 1]);
        
    }
};

 

O 풀이

상향식 DP, 재귀

class Solution {
public:
   int minCostClimbingStairs(vector<int>& cost) {
      int nSize = cost.size();
      for (int i = 2; i < nSize; i++)
         cost[i] += min(cost[i-2],cost[i-1]);
   
      return min(cost[nSize-2],cost[nSize-1]);
   }
};

class Solution {
public:
   int minCostClimbingStairs(vector<int>& cost) {
      int dp[2] = { cost.at(0), cost.at(1), };

      int nSize = cost.size();
      for (int i = 2; i < nSize; i++)
      {
         int nTemp = cost.at(i) + min(dp[0],dp[1]);
         dp[0] = dp[1];
         dp[1] = nTemp;
      }

      return min(dp[0],dp[1]);
   }
};

class Solution {
private:
    vector<int> m_cost;
    
public:
    int Climb(int nPos){
        if( nPos >= m_cost.size() )
            return 0;
        
        int nSum = m_cost[nPos];
     
        int nA = Climb(nPos+1);
        int nB = Climb(nPos+2);        
        return nSum + ( nA < nB ? nA : nB );
    }
    
    
    int minCostClimbingStairs(vector<int>& cost) {
        m_cost = cost;
        
        int nA = Climb(0);
        int nB = Climb(1);        
        return nA < nB ? nA : nB;
    }
};