Loading...
Loading...
Loading...
The college library has a tall staircase with n steps, numbered 1 to n from the bottom. For a charity drive, a volunteer stands on each step and collects a fee from anyone who stands on that step. Step i charges cost[i] rupees.
Rahul starts on the ground, below step 1. On every move he goes up 1 or 2 steps. He wants to reach the top, which is just above step n. The ground and the top charge nothing.
Print the smallest total fee Rahul can pay.
Example 1
Input
3 10 15 20
Output
15
Rahul goes from the ground to step 2 (pays 15), then jumps 2 steps to the top. The total is 15.
Example 2
Input
10 1 100 1 1 1 100 1 1 100 1
Output
6
He stands on steps 1, 3, 5, 7, 8 and 10, which cost 1 each, and skips every 100. The total is 6.
Try the problem first. Open one hint at a time.
Let best[i] be the smallest total fee paid by the moment Rahul stands on step i. The ground is step 0, with best[0] = 0.
He reaches step i from step i - 1 or step i - 2, so best[i] is cost[i] plus the smaller of those two values.
The top can be reached from step n or from step n - 1. The answer is the smaller of best[n] and best[n - 1].
The total can reach about 5 × 10^13, so use long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor