< Back




70. Climbing Stairs

We're given n, the number of steps in a staircase. We're aksed to find out how many different ways we
can climb to the stop of the staircase given that we can take 1 or 2 steps during each move.

Regular dynamic programming question. Thinking of this in terms of states, we have two choices to
make during each move, 1 step or 2 steps. And we know the previous decisions compound into the
current decision. Instead of recomputing the number of ways we've could've reached our current state,
we should just reuse previously calculated solutions.

If n is 1 or 2, we just return each value, respectively. Otherwise, we initialize a table of length
n to memoize our answers. We set the first two values to 1 and 2, respectively. Then, we iterate from
2 to n, calculating the number of ways to reach the current state by adding the number of ways to
reach T[i - 1] and T[i - 2].

Once we're done, T[n - 1], the top of the staircase, will contain the number of ways to reach the top
of the staircase.

The solution is as follows:


  class Solution:
      def climbStairs(self, n: int) -> int:
          if n == 1:
              return 1
          if n == 2:
              return 2

          T = [0] * n
          T[0] = 1
          T[1] = 2

          for i in range(2, n):
              T[i] = T[i - 1] + T[i - 2]

          return T[n - 1]


_ Time Complexity:

  O(n) - Where n is the input, n, we iterate from 2 to n to calculate the number of ways to reach the
  top of the staircase.

_ Space Complexity:

  O(n) - We maintain a table of length n to memoize our answers.