[leetcode] 746. Min Cost Climbing Stairs

문제

 

맨 아래 칸부터 하나 혹은 두 칸씩 올라가면서 최소 칸 수를 메모하며 올라간다.

 

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int start = 0;
        int top = cost.length + 2;

        int[] m_cost = new int[top];

        for(int i = 0; i < cost.length; i++) {
            m_cost[i + 1] = cost[i];
        }
        
        int[] minimum = new int[top];

        Arrays.fill(minimum, Integer.MAX_VALUE);
        minimum[0] = 0;

        // Time O(n) / Space O(n)
        while(start < top) {

            if (start + 1 < top && minimum[start + 1] > m_cost[start + 1] + minimum[start]) {
                minimum[start + 1] = m_cost[start + 1] + minimum[start];
            }

            if (start + 2 < top && minimum[start + 2] > m_cost[start + 2] + minimum[start]) {
                minimum[start + 2] = m_cost[start + 2] + minimum[start];
            }

            start += 1;
        }

        return minimum[top - 1];
    }
}