Climbing Stairs

The problem description can be found in LeetCode.

Approach

For this problem, a top-down approach comes very naturally. Also because this looks like the Fibonacci one.

We can easily find out that the problem has repeated sub-problems, and we can use memoization to save their results.

Solution

from typing import Dict


class Solution:
    def climbStairs(self, n: int) -> int:
        def dfs(i: int, memo: Dict[int, int]) -> int:
            assert i >= 0

            if i in memo:
                return memo[i]
            if i == n:
                return 1
            if i > n:
                return 0

            memo[i] = dfs(i + 1, memo) + dfs(i + 2, memo)
            return memo[i]

        return dfs(0, {})

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the number we take as input.