알고리즘
[LeetCode] 746 Min Cost Climbing Stairs JavaScript
sandwe
2022. 8. 5. 12:15
문제 링크
Min Cost Climbing Stairs - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제 유형
다이나믹 프로그래밍(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];
};