Every stair has a toll

Now each stair has a price. Stepping off a stair costs its toll, and from there you move up 1 or 2 stairs. You may start on the first or the second stair for free. What's the cheapest way to get past the top?

Same trick again: think about how you arrived. To stand on a stair, you came from the stair just below (and paid its toll) or from two below (and paid that one's toll). You'd pick whichever total is cheaper.

Counting became choosing: take the cheaper way in, don't add the two.

The start is free: reaching either of the first two stairs costs nothing.

Tolls 10, 15 and 20 · the cheapest way to stand on each stair

012top

toll

cheapest

You may start on stair 0 or stair 1 for free, so standing on either costs nothing.

Move 1 of 4

The finish line is past the last stair

A small trap: "the top" isn't the last stair, it's the landing just above it. With 3 stairs you're done when you reach position 3, which isn't a stair at all and has no toll.

So the table has one more box than there are stairs, and that last box holds the answer. With tolls 10, 15 and 20, the cheapest route starts on the 15 and jumps two stairs straight onto the landing: 15 in total.

The top is past the last stair: so the table needs one extra box.

In code

n = len(cost)
# standing on stair 0 or 1 is free
best = [0] * (n + 1)
for i in range(2, n + 1):
    best[i] = min(best[i - 1] + cost[i - 1],
                  best[i - 2] + cost[i - 2])
return best[n]