Min Cost Climbing Stairs

cost[i] is the price of stepping on stair i. Once you pay for a stair, you may climb one or two stairs. You may start on stair 0 or stair 1. The top is just past the last stair. Find the minimum total cost to reach the top.

Input:

• line 1: n
• line 2: n costs

Output: the minimum cost.

Constraints: 2 ≤ n ≤ 10⁵, 0 ≤ cost ≤ 999.

Think about it: best[i] = min(best[i−1] + cost[i−1], best[i−2] + cost[i−2]) — and you only ever need the last two values, so O(1) memory.