Problem Statement in English

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

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

Approach

Say you begin at the base of the staircase. You’re on step #0.

To go to step #1, you only have one option - you take one step, and land on step #1. To go to step #2, you have two options:

  • you go one step from step #1, and land on step #2.
  • you go two steps from step 0, and land on step #2.

These are constants, you don’t need to ever compute them again. But they form the foundation of our solution.

Let’s do step #3, just to get the hang of it:

  • one step from step #2
  • two steps from step #1

Therefore, to get to step #3, we have: sum(# solutions to get to step #1, # solutions to get to step #2).

Do you see a pattern? The solution to the nth step always depends on the sum of solutions to the n-1th and n-2th problems.

Solution in Python

class Solution:
    def climbStairs(self, n: int) -> int:
        @cache
        def dp(step):
            if step == n:
                return 1
            elif step > n:
                return 0

            return dp(step + 1) + dp(step + 2)

Complexity

  • Time: $O(n)$
    This is is because we only run the algorithm until we get to the nth step.

  • Space: $O(n)$
    We store the results of all subproblems in a cache, which can grow linearly with the input size.

And we are done.