Min Cost Climbing Stairs

퇴근하고 여유가 많은데 운동도 갔다오고 그냥 멍하니 있다보니깐 시간이 너무 빨리가서 현타도 자주온다. 그래도 새로운 기술을 회사에서 계속 배우고 있으니 백엔드 기술은 조금 뒤로하고 개인역량을 키우기 위해 리트코드에서 문제 패키지로 만들어준 Ultimate DP Study Plan을 정복하려고 목표를 잡았다 (하루 2문제)

정말 DP 마스터 해보고 싶다..오늘 푼 문제는 스터디 플랜을 따라가야 하기때문에 Easy 문제다. 예전에도 물론 이 문제를 풀었던 경험이 있지만 그때는 Memoization 방식으로 풀었고 실제로 많이 사용되는 Tabulation 방식에 더 익숙해지려고 새롭게 풀어봤다.

계단을 하나, 혹은 둘만 오를 수 있는 조건에서 가장 낮은 코스트로 끝까지 올라가야 하는 문제다. DP 문제에서 가장 큰 역량은 중복되는 구간을 어떻게 저장하냐에서 갈리는거 같다. 나같은 경우 점프 구간에서 값을 업데이트 할때 하나 혹은 두개 전에 값에서 본인을 포함하여 값을 올리는 방향으로 설정했다. 나중에 더 심화된 문제에서 선택하냐 아니면 선택하지 않냐로 진화하겠지만 그래도 기본을 다루기에 충분히 좋은 문제였다.

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        if(cost.length == 2) return Math.min(cost[0],cost[1]); 
        int[] dp = new int[cost.length + 1]; 
        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]); 
    }
}

간단한 코드여서 오늘은 그냥 자바로만 올린다.