[LeetCode] 746 Min Cost Climbing Stairs JavaScript

문제 링크

Min Cost Climbing Stairs - LeetCode

 

문제 유형

다이나믹 프로그래밍(Dynamic Programming)

 

문제 풀이

해당 문제는 각 계단을 올랐을 때의 비용을 나타내는 숫자 배열이 주어지고, 계단을 다 올랐을 때의 최소 비용을 구하는 문제이다. 계단은 1칸 또는 2칸을 오를 수 있다.

생각해보면 출발 지점의 비용은 없으므로 Index 0과 Index 1 계단까지 올라가는 최소 비용은 0이다. 그리고 계단은 1칸 또는 2칸 오를 수 있으므로 Index i 계단에 오르는 방법은 Index (i - 1) 계단에서 1칸 올라가는 것과 Index (i - 2)에서 2칸 올라가는 것, 즉 총 2가지이다. 그러므로 Index i 계단에 오르는 비용의 경우는 Index (i - 1)까지 올라가는 비용 + Index (i - 1)의 비용, Index (i - 2)까지 올라가는 비용 + Index(i - 2)의 비용이고, 이 둘중 더 작은 비용이 최소 비용이 된다.

 

코드

var minCostClimbingStairs = function(cost) {
    const dp = new Array(cost.length + 1);
    dp[0] = 0, dp[1] = 0;
    
    for (let i = 2; i < dp.length; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[dp.length - 1];
};

 

참고

https://www.youtube.com/watch?v=lhZTYwHgrDM