Back to solutions

Climbing Stairs

EasyDynamic Programming

You can climb 1 or 2 steps at a time. Count the distinct ways to reach the top of n stairs.

Open problem
Constraints
  • 1 <= n <= 45

Fibonacci-style DP

Time O(n)Space O(1)

Ways to reach step i equal the ways to reach i-1 plus i-2. Track the last two values and roll forward, which is the Fibonacci sequence.

int climbStairs(int n) {
    int a = 1, b = 1;
    for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; }
    return b;
}