Min Cost Climbing Stairs
Easy · Dynamic Programming · Array · Dynamic Programming
Problem
You are given an integer array cost where cost[i] is the fee you pay to stand on step i of a staircase. After paying for a step you may move up either one or two steps.
You may begin on step 0 or step 1 without paying anything beforehand. The top of the staircase is the position just past the last step (index n).
Return the minimum total fee needed to reach the top.
Examples
Input: cost = [5,1,4,2,8] Output: 3
Start on step 1 (pay 1), jump to step 3 (pay 2), then jump two steps to the top: 3 in total.
Input: cost = [3,3] Output: 3
Either starting step costs 3, and one climb from it reaches the top.
Input: cost = [0,7,0,7,0] Output: 0
Stand only on the free steps 0, 2 and 4, jumping two at a time.
Constraints
- 2 <= len(cost) <= 1000
- 0 <= cost[i] <= 999
Approaches
- Baseline: plain recursion — time O(φ^n), about 1.62^n, space O(n) for the call stack
Follow-up
This is the cost version of Climbing Stairs: the same two-term recurrence with min and a fee instead of +. The use cases let you jump up to k steps (a sliding-window minimum keeps it linear) and count how many climbs achieve the minimum (carry a count beside each minimum).
Related problems
Start free on Cariara · Coding problems · System design studio
