Min cost climbing stairs

Cheapest way to reach the top of a staircase, paying the cost of a step each time you leave it, moving 1 or 2 steps at a time.

The idea

The top is one step past the last stair, and it can be reached for free starting from either step 0 or step 1. dp[i] is the cheapest cost to reach step i; it comes from paying to leave step i-1 or paying to leave step i-2, whichever is cheaper.

Code

public static int MinCostClimbingStairs(int[] cost) {
    int n = cost.Length;
    var dp = new int[n + 1];
    dp[0] = dp[1] = 0;
    for (int i = 2; i <= n; i++)
        dp[i] = Math.Min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    return dp[n];
}

Tips

• dp[0] and dp[1] both start at 0: you may begin the climb at either step without charge.
• Only the previous two values are ever read, so two variables can replace the whole array.

In the .NET library

The cost is charged when you leave a step, not when you land on it. That is why dp[i] adds cost[i-1] or cost[i-2], the cost of the step being left, not of step i itself.