Cheapest Way Up the Stairs

L8 Hard Dynamic Programming

Concept

When the best future depends only on the previous two steps, you can build the answer with two rolling variables instead of a full table.

You are on the floor before index 0 of cost. From index i you may climb 1 or 2 steps into i + 1 or i + 2, paying cost[i] when you land. Reach the floor past the last index (the top) at minimum total cost.

Examples

▸ cost = [10, 15, 20]

→ 15

▸ cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

→ 6

▸ cost = [0, 0, 0, 0]

→ 0

Progressive Hints

Hint 1 · Nudge

You reached this step from one step back or two, so pay this step and add the cheaper arrival.

Hint 2 · Plan

Let best[i] be the minimum total cost to reach and pay for step i. best[i] = cost[i] + min(best[i-1], best[i-2]). Since you can leave from either of the last two steps, the answer is the minimum of the last two bests.

Hint 3 · Approach

Hold the best cost for two steps back and one step back. For each step i, the current cost is cost[i] plus the smaller of the two, then slide both forward. Return the smaller of the final two.

Output

// Run your code to see the output here.