Min Cost Climbing Stairs

Difficulty: Easy

Problem

Each stair has a toll: cost[i] is paid when you step OFF stair i (hopping 1 or 2 stairs). You may start on stair 0 or stair 1 for free. Find the minimum total cost to reach the top (one past the last stair). Climbing Stairs asked HOW MANY ways — this asks for the CHEAPEST one.

Example

Input: cost = [10,15,20]
Output: 15
Explanation: Start on stair 1 (free), pay 15, hop two to the top. Starting at 0 would cost at least 10 + something.

Brute-force approach

The naive recursion is taught inside the guided walkthrough — same explosion as Climbing Stairs, same two cures.

Optimal approach

Key insight: Climbing Stairs with money: the last-hop split is identical, but counting's + becomes optimizing's min. Change the combiner, keep the skeleton.

Bottom-up over positions 0..n: each position takes the cheaper of its two possible arrivals (previous stair + its toll, or two back + its toll).

Steps

1. State: dp[i] = min cost to stand at position i; dp[0] = dp[1] = 0 (free starts)
2. Transition: dp[i] = min(dp[i−1] + cost[i−1], dp[i−2] + cost[i−2])
3. Fill left to right up to position n (the top)
4. dp[n] is the answer; roll to two variables for O(1) space

Time complexity: O(n) · Space complexity: O(1) with rolling variables