LeetCode - 746. Min Cost Climbing Stairs

문제

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

---

풀이

기초적인 DP 문제이다.

한번에 올라갈 수 있는 계단의 수는 한칸 또는 두칸이며, 해당 칸을 밟을 경우 그만큼의 코스트를 사용한다.

이 때, 최소 코스트를 사용하여 가장 윗 칸까지 이동하면 된다.

다음 칸으로 갈 때 최소 코스트는, 두 칸 밑과 한 칸 밑을 비교하여 더 작은 코스트를 선택하면 된다.

---

코드

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int []dp = new int[len];

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

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

        return Math.min(dp[len-1], dp[len-2]);
    }
}

---