100.Min Cost Climbing Stairs

Easy1-D Dynamic Programming · 2/12

Problem

You are given an integer array cost where cost[i] is the price of stepping on stair i. After paying cost[i] you may climb either one or two stairs.

You may start on stair 0 or stair 1 for free (you still pay that stair's cost when you leave it). The "top" is the position just past the last stair, index n = cost.length. Return the minimum total cost to reach the top.

Examples

Input:  cost = [10, 15, 20]
Output: 15
Explanation: Start on stair 1, pay 15, climb two stairs to the top.

Input:  cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Start on stair 0 and step on 0, 2, 4, 6, 7, 9 — paying 1 six times — then climb to the top.

Constraints

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

💡 Key Insight

Define f(i) = minimum cost to arrive at position i (not yet paying cost[i]). You arrive at i from i - 1 (paying cost[i - 1]) or from i - 2 (paying cost[i - 2]), so f(i) = min(f(i - 1) + cost[i - 1], f(i - 2) + cost[i - 2]) with f(0) = f(1) = 0 because you can start on either for free. The answer is f(n). Like Climbing Stairs, each state needs only the previous two, so two variables suffice.

Recursion (Brute Force)

TimeO(2ⁿ)SpaceO(n)

Intuition

To stand at position i you made a final jump from i - 1 or i - 2. Try both, recursively compute the cheapest way to reach those earlier positions, and take the minimum.

Recurrence: f(i) = min(f(i - 1) + cost[i - 1], f(i - 2) + cost[i - 2]), f(0) = f(1) = 0.

Algorithm

dfs(i): if i <= 1, return 0 (free starting stairs).
Return min(dfs(i - 1) + cost[i - 1], dfs(i - 2) + cost[i - 2]).
Answer is dfs(n).

Visualization

cost = [10, 15, 20, 5], n = 4. f(2) appears twice and f(1)/f(0) many times.

flowchart TD
    A["f(4)"] -->|"+cost[3]=5"| B["f(3)"]
    A -->|"+cost[2]=20"| C["f(2)"]
    B -->|"+cost[2]=20"| D["f(2)"]
    B -->|"+cost[1]=15"| E["f(1) = 0"]
    C -->|"+cost[1]=15"| F["f(1) = 0"]
    C -->|"+cost[0]=10"| G["f(0) = 0"]
    D -->|"+cost[1]=15"| H["f(1) = 0"]
    D -->|"+cost[0]=10"| I["f(0) = 0"]

f(2) = 10, f(3) = min(10 + 20, 0 + 15) = 15, f(4) = min(15 + 5, 10 + 20) = 20.

Code

java

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        return dfs(cost, cost.length);
    }

    // minimum cost to arrive at position i
    private int dfs(int[] cost, int i) {
        if (i <= 1) {
            return 0; // may start on stair 0 or 1 for free
        }
        int fromOne = dfs(cost, i - 1) + cost[i - 1];
        int fromTwo = dfs(cost, i - 2) + cost[i - 2];
        return Math.min(fromOne, fromTwo);
    }
}

Complexity

Time: O(2ⁿ) — two recursive branches per call.
Space: O(n) — recursion depth.

Top-Down Memoization

TimeO(n)SpaceO(n)

Intuition

f(i) is the same no matter which path asked for it. Cache it in memo[i] so every position is solved once.

Algorithm

memo of size n + 1 filled with -1.
dfs(i): base case i <= 1 → 0; if memo[i] != -1 return it.
Compute with the recurrence, store in memo[i], return.

Dry Run

cost = [10, 15, 20]
dfs(3) → dfs(2) → dfs(1)=0, dfs(0)=0 → memo[2] = min(0+15, 0+10) = 10
       dfs(3) = min(memo[2] + 20, dfs(1) + 15) = min(30, 15) = 15

Code

java

import java.util.Arrays;

class Solution {
    private int[] memo;

    public int minCostClimbingStairs(int[] cost) {
        memo = new int[cost.length + 1];
        Arrays.fill(memo, -1);
        return dfs(cost, cost.length);
    }

    private int dfs(int[] cost, int i) {
        if (i <= 1) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        memo[i] = Math.min(dfs(cost, i - 1) + cost[i - 1],
                           dfs(cost, i - 2) + cost[i - 2]);
        return memo[i];
    }
}

Complexity

Time: O(n) — n + 1 states, O(1) each.
Space: O(n) — memo array and recursion stack.

Bottom-Up Tabulation

TimeO(n)SpaceO(n)

Intuition

Fill dp[i] from left to right. dp[0] = dp[1] = 0, and every later cell reads two cells already filled.

Algorithm

dp of size n + 1, dp[0] = dp[1] = 0.
For i = 2..n: dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]).
Return dp[n].

Dry Run

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1], n = 10:

i	0	1	2	3	4	5	6	7	8	9	10
dp[i]	0	0	1	2	2	3	3	4	4	5	6

For example dp[3] = min(dp[2] + cost[2], dp[1] + cost[1]) = min(1 + 1, 0 + 100) = 2.

Code

java

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1]; // dp[0] = dp[1] = 0
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}

Complexity

Time: O(n) — one pass.
Space: O(n) — dp array.

Space-Optimized DPOptimal

TimeO(n)SpaceO(1)

Intuition

Only dp[i - 1] and dp[i - 2] are ever read, so replace the table with two rolling variables.

Algorithm

prev2 = 0 (dp[i - 2]), prev1 = 0 (dp[i - 1]).
For i = 2..n: curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2]); shift prev2 = prev1, prev1 = curr.
Return prev1.

Dry Run

flowchart LR
    A["cost = [10,15,20]<br/>prev2=0, prev1=0"] -->|"i=2: min(0+15, 0+10)"| B["prev2=0, prev1=10"]
    B -->|"i=3: min(10+20, 0+15)"| C["prev2=10, prev1=15"]
    C --> D["return 15"]

Code

java

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int prev2 = 0; // min cost to arrive at i - 2
        int prev1 = 0; // min cost to arrive at i - 1
        for (int i = 2; i <= cost.length; i++) {
            int curr = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

Complexity

Time: O(n) — single loop.
Space: O(1) — two integers.

Complexity Comparison

Approach	Time	Space
Recursion (Brute Force)	O(2ⁿ)	O(n)
Top-Down Memoization	O(n)	O(n)
Bottom-Up Tabulation	O(n)	O(n)
Space-Optimized DP	O(n)	O(1)

Common Pitfalls

Returning dp[n - 1] — the top is past the last stair, at index n.
Mixing up the two definitions: "cost to arrive at i" (pay the stair you leave) vs "cost to leave i" (dp[i] = cost[i] + min(dp[i-1], dp[i-2]), answer min(dp[n-1], dp[n-2])). Both work, but don't blend them.
Forgetting that both stair 0 and stair 1 are free starting points — dp[1] is 0, not cost[0].
Using 0 as the "not computed" sentinel in memoization: 0 is a valid answer, so use -1.