Min Cost Climbing Stairs

Problem

You can step on stairs with costs cost[i]. You can start at step 0 or 1 and take 1 or 2 steps at a time. Return the minimum cost to reach the top (just past the last step).

Constraints

• 2 ≤ cost.length ≤ 1000
• 0 ≤ cost[i] ≤ 999

Approach — Dynamic Programming

This is a Dynamic Programming problem. The idea: break the problem into overlapping subproblems and build the answer up, caching results so nothing is recomputed. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) to O(n²) time.

Solution code

Python

class Solution:
    def minCostClimbingStairs(self, cost):
        prev = cur = 0
        for i in range(2, len(cost) + 1):
            prev, cur = cur, min(cur + cost[i - 1], prev + cost[i - 2])
        return cur

Java

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int a = 0, b = 0;
        for (int i = 0; i < cost.length; i++) {
            int c = cost[i] + Math.min(a, b);
            a = b; b = c;
        }
        return Math.min(a, b);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.