[Leetcode(릿코드)] 746. Min Cost Climbing Stairs (Easy)

DP 문제

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

Min Cost Climbing Stairs - LeetCode

---

문제

Input으로 cost 배열이 주어진다

ex) cost = [10,15,20]

시작해서 배열의 마지막을 넘어서 도착해야하는데, 가장 최소의 비용으로 도달해야한다 

점프는 한번할 때, 1 또는 2로 뛸 수 있다

예를들어, [10,15,20]일 때, [시작 10 15 20 도착] 이다

처음에 1 뛰면 10, 20, 도착 (총 30)

처음에 2 뛰면 15, 도착 (총15)

가장 최소의 비용은 15이다

 

해결

dp를 이용해 풀수있다

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        return getCheapestCost(cost);
    }
    
    private static int getCheapestCost(int[] cost) {
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int 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]);
    }
}