70. Climbing Stairs · DSA Practice

You climb a staircase of n steps, taking 1 or 2 steps at a time. In how many distinct ways can you reach the top?

Example 1

Input: n = 2

Output: 2

Example 2

Input: n = 3

Output: 3

Hint 1

The last move is 1 step or 2 steps, so ways(n) = ways(n−1) + ways(n−2).

Hint 2

That is the Fibonacci recurrence; keep only two variables.

Dynamic Programming

Approach 1: Plain recursion

Recomputes the same subproblems.

⏱ Time O(2ⁿ)💾 Space O(n)

Approach 2: Memo / tabulation

Store each ways(i) once.

⏱ Time O(n)💾 Space O(n)

Approach 3: Two variables ✅

Only the last two values are needed.

⏱ Time O(n)💾 Space O(1)

Reference solution for Two variables (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1               # ways(0), ways(1)
        for _ in range(n - 1):
            a, b = b, a + b       # ways(i) = ways(i-1) + ways(i-2)
        return b

class Solution {
    public int climbStairs(int n) {
        int a = 1, b = 1;               // ways(0), ways(1)
        for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; }
        return b;
    }
}

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 1;               // ways(0), ways(1)
        for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; }
        return b;
    }
};

function climbStairs(n) {
  let a = 1, b = 1; // ways(0), ways(1)
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Dynamic Programming (1-D).