Min Cost Climbing Stairs

Problem

You are given an array cost where cost[i] is the price of stepping on stair i. Once you pay for a stair you may move up either one or two stairs. You may begin on stair 0 or stair 1 without paying anything to get there (you pay for a stair only when you step on it). The goal is the landing just past the last stair, which costs nothing. Return the minimum total you must pay to reach the landing.

• cost has at least two stairs and up to about a thousand.
• Each stair's cost is a non-negative integer under a thousand.

Examples

• cost = [8, 12, 25] → 12. Start on stair 1 (pay 12) and jump two stairs to the landing.
• cost = [2, 50, 2, 2, 2, 50, 2, 2, 50, 2] → 12. Start at stair 0 and take stairs 0, 2, 4, 6, 7, 9 (all cost 2), skipping every 50.
• cost = [7, 7] → 7. Start on either stair and step off.

Hints

1. To reach any stair i, you must have come from i-1 or i-2. Which of those two should you have come from?
2. The landing is one stair past the end; treat it like a stair with cost 0.
3. min_to[i] = cost[i] + min(min_to[i-1], min_to[i-2]), with min_to[0] = cost[0] and min_to[1] = cost[1], and the answer is min(min_to[n-1], min_to[n-2]).