Climbing Stairs

Problem

You are climbing a staircase with n steps. Each move you can take 1 or 2 steps. How many distinct ways can you reach the top?

Constraints

• 1 ≤ n ≤ 45

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 climbStairs(self, n):
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a

Java

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int oneStepBefore = 2;
        int twoStepsBefore = 1;
        for (int i = 3; i <= n; i++) {
            int current = oneStepBefore + twoStepsBefore;
            twoStepsBefore = oneStepBefore;
            oneStepBefore = current;
        }
        return oneStepBefore;
    }
}

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.