Cheapest Climb to the Top

Easy

A staircase has steps 0, 1, …, n - 1, and standing on step i costs fees[i]. The top lies just past the last step and is free. From the floor you may step straight onto step 0 or step 1. After paying for a step, you move up either one step or two. Return the smallest total you have to pay to reach the top.

Example 1

fees=[4, 20, 3, 30] → 7

Start on step 0 (pay 4), jump to step 2 (pay 3), then skip one step to the top. Total 7.

Example 2

fees=[8, 2] → 2

Start right on step 1, pay 2 and step onto the top.

Example 3

fees=[0, 5, 5, 0, 5] → 5

Constraints

2 ≤ len(fees) ≤ 1000
0 ≤ fees[i] ≤ 999

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Rows of the Number Pyramid Easy A Single Row of the Number Pyramid Easy Single Trade Profit Easy Alternating Team Picks Easy Water Between Walls Hard

Input

fees=[4, 20, 3, 30]

Expected

Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.