class Solution {
    // Dynamic Programming: 정상에 도달하기 위한 최소 비용
    // O(n)
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        
        // Constraints: 계단이 3개이상 일 경우에 계산이 필요하다.
        for (int i = 2; i < length; i++) {
            // 앞의 두 계단에서 더 작은 값을 합산한다.
            cost[i] += Math.min(cost[i-1], cost[i-2]);
        }
        
        //System.out.println(Arrays.toString(cost));
                
        return Math.min(cost[length - 1], cost[length - 2]);
    }
}