Summary
Compute the minimum total cost to reach the top given step costs and 1- or 2-step moves.
Problem statement
You are given a list cost where cost[i] is the cost of step i on a staircase. Once you pay the cost at a step, you can move either 1 or 2 steps forward. You can start at step 0 or step 1. The goal is to reach the top (which is beyond the last index of the list) with the minimum total cost. Write a function min_cost_climbing_stairs(cost) that returns the minimum cost to reach the top.
Task
Implement a dynamic programming solution to compute the minimum cost to reach the top of a staircase when you can take one or two steps at a time.
Examples
Simple example
Input
[10, 15, 20]
Output
15
Explanation
Start at index 1 with cost 15, then take a two-step to the top. Total = 15.
Input format
A single list of non-negative integers cost representing costs at each step.
Output format
An integer representing the minimum total cost to reach the top.
Constraints
0 <= len(cost) <= 10^5; 0 <= cost[i] <= 10^4. Aim for O(n) time and O(1) extra space.
Samples
Sample input 0
[1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Sample output 0
6
Explanation 0
Optimal path pays 1+1+1+1+1+1 = 6 by taking mostly 1-step moves and occasionally 2-steps to avoid large costs.
AI assistant
Ask me anything!
Need help? I can explain the core idea behind this problem, review your current code, and give targeted hints. Use “Teach Theory” for the concept, “Get AI hint” for a quick scaffold nudge, or ask a specific question below.
Chat history is temporary and will not be saved.
Free preview includes 1 Teach Theory response and 1 AI hint on each of the first 3 lessons in this module.