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

문제

• cost 배열에서 cost[i]는 i번째 계단을 밟을 때의 cost임
• 0번이나 1번에 계단부터 시작할 수 있음
• 1개 혹은 2개의 계단을 밟아서 올라갈 수 있음
• 계단 꼭대기까지 가는데 최소 거리를 구하기

첫 번째 시도 - Bottom Up

Intuition

i번째 계단까지의 minimum cost를 담은 배열을 sum이라고 한다면,

• Base Case: i < 2일 때, sum[i]는 cost[i]와 같음
• Recurrence Relation: i >= 2일 때, sum[i]는 sum[i-2]나 sum[i-1] 중 작은 값과 cost[i]의 합
  • 계단은 1개나 2개를 밟아서 올라갈 수 있음. i번째 계단에 가려면, i-2번째 계단에서 2칸을 올라가거나, i-1번째 계단에서 1칸을 올라가면 됨. 두 경우 모두 sum[i]에서는 cost[i]를 더해야 함. sum[i]가 최솟값이려면, i-2번째 계단까지 오르는데 최소의 cost이거나 i-1번째 계단까지 오르는데 최솟값인 경우에 해당함. 즉, sum[i-2]나 sum[i-1] 중 최솟값일 계단을 밟는 경우에 sum[i]가 최솟값이 될 수 있음.
• top에 가는 최소 cost는 sum 배열의 마지막 원소나 마지막에서 두 번째 원소 중 최솟값임. 이 두 계단에서만 한 칸이나 두 칸을 올라서 top에 오를 수 있기 때문.

Approach

• N: cost 배열의 길이
• i번째 계단까지의 minimum cost를 담은 길이가 N인 배열 sum을 선언
• i < 2일 경우, sum[i]는 cost[i]
• 2 <= i < N동안 순회하면서 다음을 반복
  • sum[i]는 sum[i-1]나 sum[i-2]중 최솟값과 cost[i]를 더한 값
• sum[N-2], sum[N-1] 중 최솟값을 반환

Complexity

• Time complexity: O(N)

  • cost 배열의 길이만큼 1번 순회

• Space complexity: O(N)

  • sum 배열의 길이가 cost 배열의 길이

Code

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    const n = cost.length;
    const sum = new Array(n);
    sum[0] = cost[0];
    sum[1] = cost[1];

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

    return Math.min(sum[n-2], sum[n-1]);
};

두 번째 시도 - 배열 초기화 없음

Intuition

• i >= 2일 경우에는 i번째 계단을 오르는데의 최솟값을 구하려면, i-1이나 i-2번째까지의 계단을 오르는 데의 minimum cost만 알면 됨

Approach

• prev2는 2번째 이전 계단까지, prev1는 1번째 이전 계단까지, cur은 현재까지의 miminum cost를 담은 변수
• base case
  • prev2는 cost[0], prev1은 cost[1]로 초기화
• 2 <= i < N을 순회하면서 다음을 반복
  • cur은 prev2와 prev1 중 최솟값과 cost[i]를 더한 값
  • prev2에 prev1 할당
  • prev1에 cur 할당

Complexity

• Time complexity: O(N)

  • cost 배열의 길이만큼 1번 순회

• Space complexity: O(1)

  • sum 배열의 길이가 cost 배열의 길이

Code

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    const n = cost.length;
    let prev2 = cost[0];
    let prev1 = cost[1];

    for(let i = 2; i < n ; i++){
        const cur = cost[i] + Math.min(prev1, prev2);
        prev2 = prev1;
        prev1 = cur;
    }

    return Math.min(prev2, prev1);
};