(Leet Code JS)Min Cost Climbing Stairs

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

Min Cost Climbing Stairs - LeetCode

 

dp 알고리즘 사용.

cost의 길이를 나타내는 length.

dp를 length의 길이만큼 할당하고 0으로 초기화.

 

계단은 1칸 또는 2칸 오를 수 있다.

그렇기 때문에 dp[0] = cost[0],

dp[1] = cost[0] + cost[1] 과 cost[1] 중 더 작은 값을 저장하고 시작한다.

 

for문은 2 ~ length만큼 반복.

점화식으로는 현재 계단의 cost + 1칸 또는 2칸 전의 cost 중 비용이 더 적은 값을 저장하면 된다.

 

dp[i] = Math.min(cost[i] + dp[i - 1], cost[i] + dp[i - 2])

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