127. Min Cost Climbing Stairs
You may begin at stair zero or stair one, then move upward one or two stairs at a time. Pay a stair's cost when leaving it and minimize the total paid before reaching the top.
The top is just beyond the final cost entry. Starting does not itself require an initial payment, so be careful about when each stair's cost is charged.
Example 1
Input
cost=[10,15,20]
Output
15
Explanation: Start at 1 and pay 15 to jump to top 3. Paying 10 then 20 costs 30.
Example 2
Input
cost=[1,100,1,1,1,100,1,1,100,1]
Output
6
Explanation: One optimal charged sequence visits indices 0,2,4,6,7,9 before the top. The cheapest first stair alone does not determine the whole route.
Example 3
Input
cost=[9]
Output
0
Explanation: Start directly at top position 1; index 0 need not be visited.
Example 4
Input
cost=[2147483647,2147483647,2147483647,2147483647]
Output
4294967294
Explanation: Any route must depart at least two charged stairs. Their total exceeds int but fits long.
Constraints
0 <= cost.length <= 1050 <= cost[i] <= 231 - 1
Hints
Hint 1
Which two stairs can immediately precede a destination t?
Hint 2
Let the state mean minimum cost to arrive, before paying to leave. What are the costs of both free starts?
Hint 3
Use min(D(t−1)+cost[t−1], D(t−2)+cost[t−2]); preserve both old registers until next is computed.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Two predecessor prices compete
[10,15,20]
15