99클럽 코테 스터디 37일차 - DP

문제

Min Cost Climbing Stairs

풀이

• 시작점을 0 또는 1에서 고를 수 있다
• step은 한 번 또는 두 번 갈 수 있다.
• 이 중 최소 비용으로 배열에 끝에 도달해야 한다.
• 배열을 순회할 때마다 최소 비용을 골라서 dp 배열에 저장한다.
• 인덱스 0 또는 1을 선택할 수 있으니 기본값으로 dp에 저장하고 계속 비교를 한다.

코드

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = cost[0];
        dp[1] = cost[1];
        
        for(int i = 2; i <= cost.length; i++){
            int c = i == cost.length ? 0 : cost[i];
            dp[i] = Math.min(dp[i - 1] + c, dp[i-2] + c);
        }
        return dp[cost.length];
    }
}

정리

• 디피는 아직 어렵다..