(C++) - LeetCode (easy) 746. Min Cost Climbing Stairs

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

Min Cost Climbing Stairs - LeetCode

dp 문제였습니다.

📕 풀이방법

📔 풀이과정

 

i번째 계단에 도착하기 위한 최소 비용을 배열 d에 저장하겠습니다.

점화식을 세워 봅니다.

$${d[i] = cost[i] + min(d[i-1], d[i-2]) (i ≥ 2)}$$계단을 한 칸 또는 두 칸 전진이 가능하므로 한 칸 전, 두 칸 전까지의 비용을 비교해 최소값을 가지고 i번째 계단으로 간다면 i번째의 비용이 더해지는 구조이므로 해당 점화식이 만들어지게 됩니다.

---

📕 Code

📔 C++

top down

class Solution {
    int d[1001];
public:
    Solution() {
        memset(d,0,sizeof(d));
    }
    int dp(int depth, vector<int>& cost) {
        if(depth < 0) return 0;
        int &ret = d[depth];
        if(ret!=0) return ret;
        ret = cost[depth] + min(dp(depth - 1, cost), dp(depth - 2, cost));
        return ret;
    }
    int minCostClimbingStairs(vector<int>& cost) {
        return min(dp(cost.size() -1, cost), dp(cost.size() -2, cost));
    }
};

bottom up

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

        return min(d[sz-1], d[sz-2]);
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.