Min Cost Climbing Stairs

Easy · 1-D Dynamic Programming

You are given an array of integers where each value is the price to step on that rung of a staircase. From a rung you may advance either one or two rungs forward, and you may begin your climb standing on rung 0 or rung 1 for free. The top of the staircase is the position just past the last rung. Return the smallest total cost needed to reach the top.

Examples

Input:  cost = [10, 15, 20]
Output: 15
Why:    Start on step index 1 (cost 15) and jump directly to the top, skipping index 2.

Input:  cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Why:    Stepping on indices 0,2,4,6,7,9 costs 1+1+1+1+1+1=6, which is the cheapest way to pass the top.

Input:  cost = [0, 0, 0, 0]
Output: 0
Why:    Every step is free so any path to the top costs nothing.

Constraints

2 <= cost.length <= 1000, 0 <= cost[i] <= 999

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Min Cost Climbing Stairs

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Min Cost Climbing Stairs. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.