ntree.ai
ntree.aiClimbing Stairs

Solutions

1. Recursion

O(2ⁿ) time | O(n) space

Intuition

As we can only climb either 1 or 2 steps, the number of ways to climb any step is the sum of two:

  • The number of ways to climb one step below it.
  • The number of ways to climb two steps below it.

We can recursively check the number of ways to climb the previous steps until we reach the first one.

Algorithm

  1. Return n when n is 1 or 2.
  2. Otherwise repeat the same steps for n - 1 and n - 2 and return their sum.
climbStairs(5)
climbStairs(4)
climbStairs(3)
climbStairs(2)
climbStairs(1)
climbStairs(2)
climbStairs(3)
climbStairs(2)
climbStairs(1)
climbStairs(5) = climbStairs(4) + climbStairs(3)
1 / 14

Code

Code
Python
def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    return climbStairs(n - 1) + climbStairs(n - 2)
/**
 * @param {number} n
 * @returns {number}
 */
var climbStairs = function (n) {
  if (n <= 2) return n
  return climbStairs(n - 1) + climbStairs(n - 2)
}
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

2. Dynamic Programming, Top Down

O(n) time | O(n) space

Intuition

As we can only climb either 1 or 2 steps, the number of ways to climb any step is the sum of two:

  • The number of ways to climb one step below it.
  • The number of ways to climb two steps below it.

We can recursively check the number of ways to climb the previous steps until we reach the first one.

To avoid repeating the same calls, we can store the number of ways for each step in a hash map.

Algorithm

  1. Create a climb function taking a number of steps and a hash map.
    • Return steps when it is 1 or 2.
    • Return the value from the hash map for steps when it is there.
    • Otherwise call climb again for steps - 1 and steps - 2, add their sum to the hash map and return it.
  2. Return climb called with n and an empty hash map.
climbStairs(5)
climbStairs(4)
climbStairs(3)
climbStairs(2)
climbStairs(1)
climbStairs(2)
climbStairs(3)
33
45
58
climbStairs(5) = climbStairs(4) + climbStairs(3)
1 / 11

Code

Code
Python
def climbStairs(n: int) -> int:
    return climb(n, {})


def climb(steps: int, known: dict[int, int]) -> int:
    if steps <= 2:
        return steps
    if steps not in known:
        known[steps] = climb(steps - 1, known) + climb(steps - 2, known)
    return known[steps]
/**
 * @param {number} n
 * @returns {number}
 */
var climbStairs = function (n) {
  return climb(n, new Map())
}

function climb(steps, known) {
  if (steps <= 2) return steps
  if (!known.has(steps)) known.set(steps, climb(steps - 1, known) + climb(steps - 2, known))
  return known.get(steps)
}
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int climbStairs(int n) {
        return climb(n, new HashMap<>());
    }

    private int climb(int steps, Map<Integer, Integer> known) {
        if (steps <= 2) return steps;
        Integer stored = known.get(steps);
        if (stored != null) return stored;
        int ways = climb(steps - 1, known) + climb(steps - 2, known);
        known.put(steps, ways);
        return ways;
    }
}

3. Dynamic Programming, Bottom Up

O(n) time | O(1) space

Intuition

As we can only climb either 1 or 2 steps, the number of ways to climb any step is the sum of two:

  • The number of ways to climb one step below it.
  • The number of ways to climb two steps below it.

We can iterate through the loop from the third step up to n, where the number of ways to each step is the sum of the ways to the two previous steps.

Algorithm

  1. Return n when n is 1 or 2.
  2. Create current and previous variables with initial values 2 and 1 respectively.
  3. Iterate through the loop from 3 to n.
    • Calculate the sum of current and previous.
    • Update previous with current, and current with the sum.
  4. Return current.
1
2
1 + 2 = 3
1 / 4

Code

Code
Python
def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    previous, current = 1, 2
    for _ in range(3, n + 1):
        previous, current = current, previous + current
    return current
/**
 * @param {number} n
 * @returns {number}
 */
var climbStairs = function (n) {
  if (n <= 2) return n
  let previous = 1
  let current = 2
  for (let step = 3; step <= n; step++) {
    const next = previous + current
    previous = current
    current = next
  }
  return current
}
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int previous = 1;
        int current = 2;
        for (int step = 3; step <= n; step++) {
            int next = previous + current;
            previous = current;
            current = next;
        }
        return current;
    }
}
def climbStairs(n: int) -> int:
    pass
 

Press Visualise to step through your code.