DSA problem
Min Cost Climbing Stairs
You are given an integer array cost where cost[i] is the cost of stepping onto the i-th stair. Once you pay the cost, you may climb either one or two stairs upward. You can start from either stair 0 or stair 1. Return the minimum total cost to reach the top of the floor — i.e., the position just past the last index.
Let dp[i] be the minimum cost incurred when you are standing on stair i (having paid cost[i] to get there). To arrive at stair i, your previous position was either stair i - 1 or stair i - 2, so dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]). The base cases reflect the free choice of starting stair: dp[0] = cost[0] and dp[1] = cost[1]. The answer is min(dp[n - 1], dp[n - 2]) because reaching the top requires one final hop from either of the last two stairs.
A natural first attempt fills an entire dp array of length n in O(n) time and O(n) space. But each entry only references the previous two, so the array is unnecessary.
The optimal approach maintains two rolling variables that track dp[i - 2] and dp[i - 1] as we sweep the array. Each iteration computes curr = cost[i] + min(prev1, prev2) and shifts the window forward, achieving O(n) time and O(1) extra space.
Examples
cost = [10,15,20]15cost = [1,100,1,1,1,100,1,1,100,1]6cost = [0,0,1,1]0Constraints
- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999
- You may start at either index 0 or index 1 without paying to get on the staircase.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.