Compute the minimum cost required to reach the top of a staircase when you may climb 1 or 2 steps at a time.
You are given an array cost where cost[i] is the cost of stepping on stair i. You can start on step 0 or step 1, and on each move you may climb either 1 step or 2 steps. After paying the cost of a step you land on, determine the minimum total cost needed to reach the position just beyond the last stair.
Return the smallest possible total cost.
Input Format
- An integer array
costof lengthn cost[i]is the cost of stepping on stairi
Output Format
- Return a single integer: the minimum total cost to reach the top
Constraints
2 <= n- Costs are non-negative integers
- You may begin from step
0or step1 - The top is the position after the last step
Example 1
Input
cost = [10, 15, 20]
Output
15
Explanation
Start at step 1, pay 15, then move directly to the top.
Example 2
Input
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output
6
Explanation
One optimal path is to pay steps 0, 2, 3, 4, 6, 7, and 9 for a total of 6.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.