Min Cost Climbing Stairs

The problem

cost[i] is the price of stair i of a staircase. You may start on stair 0 or on stair 1. Each time you stand on a stair you pay its price, and then you climb 1 or 2 stairs. The top is the floor right after the last stair, and it has no price. Return the smallest total you can pay to reach the top.

What to write

function solve(cost: number[]): number

Input
cost = [10,15,20]

Output
15

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

Output
6

Constraints

cost has at least two nonnegative entries.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   You are asked for one number, the smallest total, not for the route itself. Prices are never negative, and the top is free. Do not trust the cheaper start: in example 1, stair 0 costs less than stair 1, yet the best route starts on stair 1.

2. Hint 2: Ask a smaller question

   Take cost = [10, 15, 20] and forget the top for a moment. You arrive on stair 2. Which stairs could you have come from, and what is the least you can have paid on the way, before paying for stair 2 itself?

3. Hint 3: Name the pattern

   The least you can pay to arrive at a position depends only on the two positions below it: you came from one of them and paid its price there. Each answer is built from two smaller answers of the same kind. That is one-dimensional dynamic programming, with the smaller of two totals where Climbing Stairs had a sum. Read the lesson on one-dimensional dynamic programming.

4. Hint 4: State the invariant

   Call least(i) the smallest total paid on arriving at position i, before paying for position i itself. Then least(0) = least(1) = 0, and least(i) is the smaller of least(i - 1) + cost[i - 1] and least(i - 2) + cost[i - 2]. The top is the position i that equals the length of cost.

5. Hint 5: Sketch the pseudocode

   previous = 0, current = 0. For i from 2 up to the length of cost: cheapest = the smaller of current + cost[i - 1] and previous + cost[i - 2]; then previous = current and current = cheapest. Return current.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

The cost to reach each position is the smaller of arriving from one or two steps below. Keep only those two prior costs.

The slow way

Try every route: from each stair climb 1 stair or 2, add up the prices, and keep the smallest total. It is correct, but the number of routes grows fast: 144 for the 10 stairs of example 2 and 2,178,309 for 30 stairs. The lower stairs are added up again in route after route.

The insight

How you got to a stair does not change what comes after it. So for each position you only need one number: the least you can have paid on arriving there. You arrive from one stair below or from two below, so that number is the smaller of two sums, each built from a number you already have.

Step by step

1. Reaching stair 0 or stair 1 costs nothing: you may start on either. The total kept for a position is what you have paid before paying for that position itself. You may start on stair 0 or stair 1, so both are reached with nothing paid yet.
2. Work out each position from 2 up to the top, lowest first. A position needs the totals of the two positions below it, so those must be finished first. The top is one position past the last stair, which is why the loop goes up to the length of cost.
3. Come from one stair below or from two below, whichever costs less. Arriving from a stair costs that stair's total plus its price, which you pay for standing on it. Those are the only two ways to arrive, so the cheaper one is the least you can pay.
4. Keep only the two newest totals. The next position looks at the two positions right below it and at nothing older, so the oldest total is no longer needed.
5. Return the newest total, the least you can pay to reach the top. The last round of the loop worked out the top. Nothing is paid for the top itself, so its total is the whole price of the best route.

The same numbered steps are the comments in each solution.

function solve(cost) {
  // 1. Reaching stair 0 or stair 1 costs nothing: you may start on either
  let previous = 0;
  let current = 0;
  // 2. Work out each position from 2 up to the top, lowest first
  for (let i = 2; i <= cost.length; i++) {
    // 3. Come from one stair below or from two below, whichever costs less
    const cheapest = Math.min(current + cost[i - 1], previous + cost[i - 2]);
    // 4. Keep only the two newest totals
    previous = current;
    current = cheapest;
  }
  // 5. Return the newest total, the least you can pay to reach the top
  return current;
}

function solve(cost: number[]): number {
  // 1. Reaching stair 0 or stair 1 costs nothing: you may start on either
  let previous = 0;
  let current = 0;
  // 2. Work out each position from 2 up to the top, lowest first
  for (let i = 2; i <= cost.length; i++) {
    // 3. Come from one stair below or from two below, whichever costs less
    const cheapest = Math.min(current + cost[i - 1], previous + cost[i - 2]);
    // 4. Keep only the two newest totals
    previous = current;
    current = cheapest;
  }
  // 5. Return the newest total, the least you can pay to reach the top
  return current;
}

def solve(cost):
    # 1. Reaching stair 0 or stair 1 costs nothing: you may start on either
    previous = 0
    current = 0
    # 2. Work out each position from 2 up to the top, lowest first
    for i in range(2, len(cost) + 1):
        # 3. Come from one stair below or from two below, whichever costs less
        cheapest = min(current + cost[i - 1], previous + cost[i - 2])
        # 4. Keep only the two newest totals
        previous = current
        current = cheapest
    # 5. Return the newest total, the least you can pay to reach the top
    return current

Example 2, traced

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

Output
6

Why it works

The total kept for a position is the least anyone can pay to arrive there, because every route arrives from one of the two positions below and the cheaper of those two is taken. The first two totals are right from the start, so every later one is right too, including the top. Each answer is worked out once from two earlier answers, which is what dynamic programming means.

Time and space

Time O(n), extra space O(1). The loop runs once for each position from 2 up to the top and does a fixed amount of work each time, so the time is O(n) for n stairs. Only two totals are kept, whatever the number of stairs, so the extra space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• The top is one position past the last stair. If the loop stops at the last stair, the answer is the price of arriving there, and example 1 gives 10 instead of 15.
• Pair each total with the price of its own stair: the total from one below goes with cost[i - 1], the total from two below with cost[i - 2]. Swapping the two prices gives 20 for example 1.
• Do not pick the route one stair at a time by looking at the next two prices. In example 1 that starts on stair 0, the cheaper start, and ends up paying 25 instead of 15.

Pattern

One-dimensional dynamic programming. Builds on Climbing Stairs.

Keep going