Climbing Stairs

Problem Statement

You are given an integer n representing the number of steps to reach the top of a staircase. You can climb with either 1 or 2 steps at a time.

Return the number of distinct ways to climb to the top of the staircase.

Example 1:

Input: n = 2


Output: 2

Explanation:

  1. 1 + 1 = 2
  2. 2 = 2

Example 2:

Input: n = 3


Output: 3

Explanation:

  1. 1 + 1 + 1 = 3
  2. 1 + 2 = 3
  3. 2 + 1 = 3

Constraints:

  • 1 <= n <= 30

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of steps.

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of steps.

Hint 1

At each step, we have two choices: climb one step or climb two steps. We can solve this by considering both options and picking the minimum using recursion. However, this results in O(2^n) time complexity. Can you think of a better approach? Perhaps, try to avoid the repeated work of calling recursion more than once with same parameters.

Hint 2

This is a Dynamic Programming problem. We can use Memoization to avoid repeated work. Create an n-sized array cache to store the results of recursive calls. When the recursion is called with specific parameters, return the stored value if it has already been computed. How would you implement this?

Hint 3

We start the initial recursion with i = 0, indicating that we are at position i. We first check if the current recursion with the given i is already cached. If it is, we immediately return the stored value. Otherwise, we perform the recursion, store the result in the cache, and then return it. Can you think of the base condition to stop the recursion?

Hint 4

At each recursion, we perform two recursive calls: one for climbing one step and another for climbing two steps. The minimum return value between the two is the result for the current recursion. The base condition is to return 0 if i == n. This is a one-dimensional dynamic programming problem, which can be further optimized using more advanced techniques.

Solution

Recursion

def climb_stairs(n: int) -> int:
    def dfs(i: int) -> int:
        if i >= n:
            return i == n
        return dfs(i + 1) + dfs(i + 2)


    return dfs(0)

Time complexity: O(2 ^ n) Space complexity: O(n)

Dynamic Programming (Top-Down)

def climb_stairs(n: int) -> int:
    cache = [-1] * n
    def dfs(i: int) -> int:
        if i >= n:
            return i == n
        if cache[i] != -1:
            return cache[i]
        cache[i] = dfs(i + 1) + dfs(i + 2)
        return cache[i]


    return dfs(0)

Time complexity: O(n) Space complexity: O(n)

Dynamic Programming (Bottom-Up)

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Time complexity: O(n) Space complexity: O(n)

Dynamic Programming (Space Optimized)

def climb_stairs(n: int) -> int:
    one, two = 1, 1


    for _ in range(n - 1):
        temp = one
        one = one + two
        two = temp


    return one

Time complexity: O(n) Space complexity: O(1)

Matrix Exponentiation

def climb_stairs(n: int) -> int:
    if n == 1:
        return 1


    def matrix_mult(a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
        return [[a[0][0] * b[0][0] + a[0][1] * b[1][0],
                 a[0][0] * b[0][1] + a[0][1] * b[1][1]],
                [a[1][0] * b[0][0] + a[1][1] * b[1][0],
                 a[1][0] * b[0][1] + a[1][1] * b[1][1]]]


    def matrix_pow(m: list[list[int]], p: int) -> list[list[int]]:
        result = [[1, 0], [0, 1]]
        base = m


        while p:
            if p % 2 == 1:
                result = matrix_mult(result, base)
            base = matrix_mult(base, base)
            p //= 2


        return result


    m = [[1, 1], [1, 0]]
    result = matrix_pow(m, n)
    return result[0][0]

Time complexity: O(\log n) Space complexity: O(1)

Math

import math


def climb_stairs(n: int) -> int:
    sqrt5 = math.sqrt(5)
    phi = (1 + sqrt5) / 2
    psi = (1 - sqrt5) / 2
    n += 1
    return round((phi**n - psi**n) / sqrt5)

Time complexity: O(\log n) Space complexity: O(1)