Description

746. Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.

• Pay 15 and climb two steps to reach the top.
  The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.

• Pay 1 and climb two steps to reach index 2.
• Pay 1 and climb two steps to reach index 4.
• Pay 1 and climb two steps to reach index 6.
• Pay 1 and climb one step to reach index 7.
• Pay 1 and climb two steps to reach index 9.
• Pay 1 and climb one step to reach the top.
  The total cost is 6.

Constraints:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

---

746. 계단 오르기 최소 비용

i번쨰 계단 단계에서 오르는 비용이 정수 배열 cost로 주어집니다. 비용을 지불하면 한 단계 또는 두 단계를 오를 수 있습니다.

처음 게단 오르기를 시작 할때 인덱스 0 또는 인덱스 1의 단계에서 시작할 수 있습니다.

주어진 층의 정상(cost.length + 1)에 도달하는 최소 비용을 반환하세요.

예제 1:

입력: cost = [10,15,20]
출력: 15
설명: 인덱스 1에서 시작합니다.

• 15를 지불하고 두 계단을 올라 꼭대기에 도달합니다.
  총 비용은 15입니다.

예제 2:

입력: cost = [1,100,1,1,1,100,1,1,100,1]
출력: 6
설명: 인덱스 0에서 시작합니다.

• 1을 지불하고 두 계단을 올라 인덱스 2에 도달합니다.
• 1을 지불하고 두 계단을 올라 인덱스 4에 도달합니다.
• 1을 지불하고 두 계단을 올라 인덱스 6에 도달합니다.
• 1을 지불하고 한 계단을 올라 인덱스 7에 도달합니다.
• 1을 지불하고 두 계단을 올라 인덱스 9에 도달합니다.
• 1을 지불하고 한 계단을 올라 꼭대기에 도달합니다.
  총 비용은 6입니다.

제한 사항:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

Solution 1

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // dp 배열 초기화
        int[] dp = new int[cost.length];
        dp[dp.length - 1] = cost[cost.length - 1];
        dp[dp.length - 2] = cost[cost.length - 2];

        // 뒤에서부터 최소 비용을 계산
        for (int i = cost.length - 3; i >= 0; i--) {
            dp[i] = cost[i] + Math.min(dp[i + 1], dp[i + 2]);
        }

        // 첫 번째 또는 두 번째 단계에서 시작하는 최소 비용 반환
        return Math.min(dp[0], dp[1]);
    }
}

Solution 2

생각해보니 배열에 다 저장할 필요가 없어서 변수 2개만 남김.

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // 배열 크기가 2일 경우, 두 값 중 작은 값을 반환
        if (cost.length == 2) {
            return Math.min(cost[0], cost[1]);
        }
        
        // 마지막 두 요소로 초기화
        int secondLast = cost[cost.length - 2];
        int last = cost[cost.length - 1];

        // 마지막 세 번째 요소부터 순회 시작
        for (int i = cost.length - 3; i >= 0; i--) {
            int current = cost[i] + Math.min(secondLast, last);
            last = secondLast;
            secondLast = current;
        }

        // 최소 시작 비용 계산
        return Math.min(secondLast, last);
    }
}