Coding problem · Easy · Dynamic Programming

Climbing Stairs

Easy Algorithms & data structures Most askedSeen at Amazon, Adobe, Apple

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you reach the top?

Example 1

Input: n = 2
Output: 2
Explanation: 1+1, 2

Example 2

Input: n = 3
Output: 3
Explanation: 1+1+1, 1+2, 2+1

Constraints

1 <= n <= 45

Hints

Hint 1

The last move was either 1 step (from n−1) or 2 steps (from n−2).

Hint 2

ways(n) = ways(n−1) + ways(n−2) — Fibonacci. Keep only the last two values.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1)

Every path to step n ends with a 1-step from n−1 or a 2-step from n−2, so ways(n) = ways(n−1) + ways(n−2). Iterate bottom-up with two variables: O(n) time, O(1) space. Naive recursion without memoization is exponential.

Reference solution

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;
}

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

def climb_stairs(n: int) -> int:
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

<?php

function climbStairs(int $n): int
{
    [$a, $b] = [1, 1];
    for ($i = 2; $i <= $n; $i++) {
        [$a, $b] = [$b, $a + $b];
    }
    return $b;
}

class Solution {
    public 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;
    }
}