Cheapest climb
A staircase has len(cost) stairs, numbered from 0 at the bottom. You start on the floor, directly below stair 0, and finish on the landing, directly above the last stair. Each stride moves you up 1 or 2 positions. So your first stride lands on stair 0 or stair 1, and you can step onto the landing from either of the last two stairs.
Every stair you stand on charges a toll: cost[i] for stair i. The floor and the landing are free. Return the smallest total toll of any climb from the floor to the landing.
cost = [5, 2, 8, 1]Output3Stride 2 onto stair 1 (toll 2), stride 2 onto stair 3 (toll 1), stride 1 onto the landing. 2 + 1 = 3.
cost = [4, 4, 4]Output4Stride 2 onto stair 1, then stride 2 onto the landing. Only one stair is paid for.
cost = [3, 9, 2, 7, 1]Output6Stand on stairs 0, 2 and 4: 3 + 2 + 1 = 6. The 9 and the 7 are both stepped over.
2 ≤ len(cost) ≤ 500
0 ≤ cost[i] ≤ 999
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.