[LeetCode] Min Cost Climbing Stairs

문제링크

Min Cost Climbing Stairs - LeetCode

 

이동을 위한 cost값이 요소로 들어있는 cost 배열이 주어질때 cost 배열을 끝까지 가는데 소요되는 비용을 구하는 문제이다.

조건 : 한번에 index 1칸 또는 2칸을 건널 수 있다.

접근 방법

전형적인 dp 문제이다.

점화식 => dp[i] += Math.min(dp[i-1], dp[i-2]) + cost[i]
dp[i-1], dp[i-2]는 현재까지 지불한 비용이고, cost[i]는 현재 위치에서의 비용이다.

dp[0] = cost[0];
dp[1] = cost[1];

for(let i = 2; i < cost.length; i++){
    dp[i] += Math.min(dp[i-1], dp[i-2]) + cost[i];
}​

테스트케이스를 통해 예를 들면
[1,100,1,1,1,100,1,1,100,1]을 점화식을 통해 값을 도출하면 아래와 같은 값이 나온다.
[1, 100, 2, 3, 3, 103, 4, 5, 104, 6]


※ 다른 풀이
dp 배열을 따로 생성하지 않고 뒤에서부터 값을 찾는 방법을 발견하였다.

for (let i = cost.length - 3; ~i; i--){
    cost[i] += Math.min(cost[i+1], cost[i+2])
}​

따로 배열을 생성하지 않아 메모리 효율성이 더 좋은 코드이다.

[1,100,1,1,1,100,1,1,100,1]을 코드를 돌리면 아래와 같은 값이 나온다.
[6, 105, 5, 5, 4, 102, 3, 2, 100, 1]

 

// 나의 풀이

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

 

// 다른 풀이

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    for (let i = cost.length - 3; ~i; i--){
        cost[i] += Math.min(cost[i+1], cost[i+2])
    }
    return Math.min(cost[0], cost[1])
};