Min Cost Climbing Stairs

Find the cheapest way to the top of a staircase where every step you stand on has a price.

Each step of a staircase has a price, given in an array cost, where cost[i] is what you pay for standing on step i. After paying for a step, you climb one or two steps up. You may start on step 0 or step 1 without paying anything first. Return the smallest total price to reach the top, which is the place just past the last step.

Example 1
Input: cost = [10, 15, 20]
Output: 15
Explanation: start on step 1, pay 15, climb two steps to the top.
Example 2
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: stand on steps 0, 2, 4, 6, 7 and 9, which avoids every 100.
Solution

The Idea

Picture a staircase where every step asks for a fee when you stand on it, and the landing at the top is free. You may take the steps one at a time or skip one, and you want to arrive at the top having paid as little as possible.

In Example 1 the staircase has three steps, with prices 10, 15 and 20, so the top is step 3. Starting on step 0 and standing on every step costs 10 + 15 + 20 = 45. Starting on step 0 and skipping to step 2 costs 10 + 20 = 30. Starting on step 1 costs only 15, because two steps up from step 1 is already the top.

With three steps there are only a few routes to compare. Example 2 has ten steps and far more routes. So how do we find the cheapest route without trying them all?

Turn the question around. Instead of following routes upward, ask about one step at a time: what is the least you must have paid to stand on step i, before paying its own price? Call that the cheapest cost to stand on step i. For step 0 and step 1 it is 0, since you may start there. Any higher step is reached from one or two steps below it. So its cheapest cost is the smaller of two sums: the step below's cheapest cost plus that step's price, or the same for the step two below.

Look at the picture below, which fills in these cheapest costs for Example 1.

The stairs of Example 1: step 0 with price 10, step 1 with price 15, step 2 with price 20, and the top as step 3. The cheapest costs to stand on them are 0, 0, 10 and 15. The top is reached for 0 + 15 = 15 from step 1, cheaper than 10 + 20 = 30 from step 2.

The bottom row, labelled "cheapest cost to stand here, before paying", starts with 0 and 0 for step 0 and step 1. Step 2 can be reached from step 1 for 0 + 15 = 15, or from step 0 for 0 + 10 = 10, so its box holds 10. For the top, the orange arrow from step 1 costs 0 + 15 = 15 and the dashed arrow from step 2 costs 10 + 20 = 30. The top's box holds the smaller sum, 15, which is the answer.

So each step's cheapest cost needs only the two values just below it, and each value is worked out once. Building the top's answer this way, from a table of stored answers for the lower steps, is called dynamic programming.

Solution Approach

A method that tries every route gets the right answer but is slow, and the table avoids that. Turning the table into code means settling four things: what one entry holds, how it follows from the two below, where the table starts, and how much to keep.

Trying every route

What happens if we skip the table? A method can work out the cheapest cost to stand on step i by calling itself for step i - 1 and step i - 2. Those calls call themselves again, down to step 0 and step 1. It gives the right answers, but the same lower steps are worked out over and over. For the ten steps of Example 2 it makes 177 calls. For 30 steps it makes 2,692,537 calls, and for 40 steps 331,160,281.

What one entry means

What should the table store? Write dp[i] for the cheapest cost to stand on step i, before paying cost[i]. With n = cost.length steps, the top is step n, so the table has n + 1 entries and the answer is dp[n].

From two entries to the next

How does dp[i] follow from the entries below it? The last move onto step i came either from step i - 1, paying cost[i - 1], or from step i - 2, paying cost[i - 2]. So dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]).

Where the table starts

Which entries need no rule? Step 0 and step 1 are free starting places, so dp[0] = dp[1] = 0, and the rule fills everything from step 2 up. For Example 2 the full table reads 0, 0, 1, 2, 2, 3, 3, 4, 4, 5, 6, so dp[10], the top, is 6.

Keeping only two numbers

Do we need the whole table? The rule for step i reads only dp[i - 1] and dp[i - 2], so once a step's value has been used twice it is never read again. Two variables are enough, moved up one step at a time, just as in Climbing Stairs.

Java Solution

The method minCostClimbingStairs works in these steps:

  1. First, set twoBelow and oneBelow to 0. They start as the cheapest costs to stand on step 0 and step 1, which are both free.
  2. A loop moves i from step 2 up to cost.length, the top. The condition is i <= cost.length, so the last pass works out the top itself.
  3. Inside the loop, here gets the cheapest cost to stand on step i: the smaller of oneBelow + cost[i - 1] and twoBelow + cost[i - 2].
  4. Then both variables move up one step: twoBelow takes the value of oneBelow, and oneBelow takes here.
  5. When the loop ends, oneBelow holds the cheapest cost to stand on the top, and the method returns it.

The main method runs both examples, a staircase of two steps, and four steps that all cost 4.

Java
public class MinCostClimbingStairs {

    public static int minCostClimbingStairs(int[] cost) {
        int twoBelow = 0;                        // cheapest cost to stand on step 0
        int oneBelow = 0;                        // cheapest cost to stand on step 1
        for (int i = 2; i <= cost.length; i++) { // step cost.length is the top
            int here = Math.min(oneBelow + cost[i - 1], twoBelow + cost[i - 2]);
            twoBelow = oneBelow;
            oneBelow = here;
        }
        return oneBelow;
    }

    public static void main(String[] args) {
        System.out.println(minCostClimbingStairs(new int[] {10, 15, 20}));
        System.out.println(minCostClimbingStairs(new int[] {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));
        System.out.println(minCostClimbingStairs(new int[] {5, 3}));
        System.out.println(minCostClimbingStairs(new int[] {4, 4, 4, 4}));
    }
}

Running it prints:

Output
15
6
3
8

The 15 and the 6 match the answers of Example 1 and Example 2. The 3 comes from [5, 3]: the loop runs once, for the top, and picks 0 + 3 from step 1 over 0 + 5 from step 0.

Look at the last line, 8. With four steps that all cost 4, the cheapest route skips every other step and pays twice, for example on step 1 and step 3. The table behind it reads 0, 0, 4, 4, 8.

The <= in the loop condition matters, because the top is one place past the last step. With i < cost.length instead, the loop stops after step 2, and Example 1 returns 10, the cheapest cost to stand on step 2, instead of 15.

The original implementation, MinCostClimbingStairs.java, is on GitHub.

Complexity

The work is one climb up the stairs, with the same small amount of work on each step.

  • Time: O(n), because the loop runs once for every place from step 2 to the top, n - 1 times for n prices, with two additions and one Math.min each time.
  • Space: O(1), because only twoBelow, oneBelow and here are kept however long the staircase is, while a full table would hold n + 1 entries.

The same pattern of choosing between the two previous entries appears in House Robber, with a maximum instead of a minimum.