A staircase has n stairs indexed 0 to n-1. Standing on stair i and taking a step charges you cost[i] (the toll is paid when you leave the stair, not when you arrive). From stair i a single step moves you to stair i+1 or stair i+2.
You may begin standing on either stair 0 or stair 1 (arriving there is free). The top is the position just past the last stair (index n). Return the minimum total toll to reach the top.
Line 1: an integer n, the number of stairs.
Line 2: n space-separated non-negative integers, cost[0..n-1].
A single integer: the minimum total toll to reach the top.
Example 1
Input
10 1 100 1 1 1 100 1 1 100 1
Expected
6
Explanation
Step onto stairs 0, 2, 4, 6, 7, 9 (paying 1 each of six times) and then off the top: total toll 6. No route is cheaper.
Example 2
Input
2 5 3
Expected
3
Explanation
Start on stair 1 (free) and step off it paying 3, reaching the top. Starting on stair 0 would cost 5, so 3 is best.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →