All problems

Min Cost Climbing Stairs

Easy · dynamic programming

A staircase has one step per entry of cost. Whenever you stand on step i you pay cost[i], and you pay it each time you land there.

You may begin on step 0 or step 1. From any step you can climb 1 or 2 steps at a time. The top of the staircase is one place past the last step, and reaching it costs nothing. You get there by climbing from either of the last two steps.

Return the smallest total cost to reach the top.

Examples

Example 1

Input: cost = [10, 15, 20]

Output: 15

Start on step 1 (pay 15), then climb 2 steps to the top.

Example 2

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

Output: 6

Land on steps 0, 2, 4, 6, 7 and 9, skipping every 100. That costs 1 + 1 + 1 + 1 + 1 + 1 = 6.

Example 3

Input: cost = [5, 5]

Output: 5

Start on either step and climb to the top: 2 steps from step 0, or 1 step from step 1.

Constraints