# Interview - Emily Chen

## Question
You are given an array of integers cost where cost[i] is the cost at the ith step on a staircase. Starting at either index 0 OR 1, you can either climb one or two steps each time. Return the minimum cost to reach the end of the staircase.
Note: You pay the cost at the current step only when moving to the next

## Examples
`Input: cost = [10,20,15]`

`Output: 20`

`Explanation: Start at 20, take 2 steps, reach the top, pay 20.`

`Input: cost = [1,100,1,1,1,100,1,1,100,1]`

`Output: 6`

`Explanation: Start at 1, take 2 steps, pay 1, take 2 steps, pay 1, take 2 steps, pay 1, take 1 step, pay 1, take 2 steps, pay 1, take 1 step, reach the top, pay 1.`

## Code

public int minCost(int[] costs) {
    // initialize totalSum = 0
    // minSumSoFar
    // iterate through the array
    //     if arr[i] + arr[i+2] <= arr[i+1] 
    //            then step to arr[0] + arr[2], and incrememnt counter
    //     else: step to arr[1]
    
    // cost = [10, 20, 15, 300, 1]
    
    // arr[i] -> arr[i - 1] or arr[i - 2]
    
    // ans[i] -> ans[i-1] or ans[i-2]
    
    // ans[i] = min(ans[i-2] + arr[i], ans[i-1] + arr[i])
    
    // minValues = {10, 20, 25, 320, 26} -> 26
    
    int[] minValues = new int[costs.length];
    
    minValues[0] = costs[0];
    minValues[1] = costs[1];
    for (int i = 2; i < costs.length; i++) {
        minValues[i] = Math.min(minValues[i-2] + costs[i], minValues[i-1] + costs[i]);
    }
    
    return Math.min(minValues[costs.length - 1], minValues[costs.length - 2]);
}