70 — Climbing Stairs
Restating Info We’re Already Given:
- We are climbing an n step staircase
- Each time we can climb 1 or 2 steps
- 1 ≤ n ≤ 45
Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):
- Do we have any space constraints?
- Should we store intermediate results?
- Do you care if I build the solution bottom-up vs top-down?
Discuss Naive Solution:
The base case is when n ≤ 2. In that case, the number of ways is equal to the number of steps. If the current step can be reached from the 1 and 2 steps below, then the current step’s value is the sum of the value for 1 step below and 2 steps below. Naively, we could just sum that until we reach n:
This solution works in theory, but is extremely costly in practice as we have to recompute climbStairs(n) many times for the same n. Suppose n = 10: we recursively calculate climbStairs(9) + climbStairs(8), which recursively calculates climbStairs(8) + climbStairs(7) and climbStairs(7) + climbStairs(6), and so forth. The expression tree grows exponentially, which is bad.
Discuss Alternative Solution:
Not all is lost with the above solution — we can cache intermediate results and speed up the above solution (by a lot). To do so, we can either use a dictionary or a list.
Discuss Optimal Solution:
Both the above solutions use O(n) space. However, at any given time, we only need to cache the 2 previous values (i.e. the number of unique ways to get to the n-1 and n-2 stairs. Therefore, we can build the solution bottom-up with just these 2 variables.
Code Optimal Solution:
Runtime/Space Complexity:
The optimal solution has a linear runtime as we have 1 for loop that decrements by 1 from n to 2. There’s 2 integer variables, so space is constant.
Test Cases:
- n ≤ 0: question constraint is: 1 ≤ n ≤ 45
- n == 1 and n == 2: check base cases
- any other n from 3 to 45: ensures iteration works
