Problem 70

(Last updated: )

Question statement:

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution

Though this problem keeps yelling dynamic programming in our faces, we will provide three increasingly more efficient solutions (the second of which is a dp solution).

Main idea - approach 1:

Cut away all programattic instincts, and look at this as a purely combinatorial problem. We split the solution into cases indexed by the number $k$ of “2 steps” we take on our way to get to the top.

  • Case $k=0$: This can be done exactly $1 = {n \choose 0}$ ways.
  • Case $k=1$: In this case, we are allowed to take one “2 step” and $n-2$ regular steps. This is the same as filling n-1 spots with all but one ones and exactly one 2. The number of ways to do this is $$n-1 = {n-1 \choose 1}$$
  • Case $k = 2$: In thise case, we have two “2 steps” and $n-4$ regular steps. This is the same as filling n-2 spots with all but two ones, and exactly two 2s. The number of ways to do this is $${n-2 \choose 2}$$
    and so on until $k=\lfloor n/2\rfloor$.

Thus the total number of ways is equal to
$$T_n = \sum_{k=0}^{\lfloor n/2 \rfloor} {n-k \choose k} \qquad (\star)$$

This is a bad solution computationally because to calculate ${n \choose r}$ via the pascal’s triangle, we need to generate a pascal’s triangle which involves $\sum_{k=1}^n k(k+1)$ operations, which is O($n^3$) operations.

Unrelated update: This github issue/resolution has some really cool ideas to optimize computing the binomial coefficient. So the inbuilt comb() is optimized to be far better than the Pascal’s triangle approach, it looks like.

Main idea - approach 2:

Approach 1 is not all that bad if we could find a closed form expression for $(\star)$, then it would essentially be an $O(1)$ computation (or at worst O(log(n)) if exponentials are involved). Funnily enough, this closed form is most naturally obtained by actually thinking about a dp approach to this problem. In particular, the key realization is as follows: To get to the $k^{th}$ step, we could take one step from the $(k-1)^{th}$ step, or a “2 step” from the $(k-2)^{th}$ step. Thus $T_k = T_{k-1} + T_{k-2}$ - and then it occurs to us:

$$\texttt{Fibonacci.}$$

So, when the excitement subdues, we realize $T_n = F_{n+1}$ where $F_r$ is the $r^{th}$ Fibonacci number.

Note: It is $F_{n+1}$ because we need to initialize the Fibonacci sequence with an extra 1 to kickstart the recursion, which corresponds to climbing 0 stairs – which is not a valid field condition.

Main idea - approach 3:

Now our math brains kick in, and reminds us that $F_n$ has a closed form expression, namely:

$$F_r = \frac{1}{\sqrt{5}}\left[\phi^r - \phi^{-r}\right]$$
where $\phi$ is the golden ratio, with value
$$\phi = \frac{1+\sqrt{5}}{2}$$

which is a pretty slick solution.

Code:

Approach 1:

1
2
3
4
5
6
def climbStairs1(self, n: int) -> int:
    limit = n//2+1
    res = 0
    for i in range(limit+1):
        res += comb(n-i, i)
    return res

Approach 2:

1
2
3
4
5
def climbStairs(self, n: int) -> int:
    fib = [1,1]
    for i in range(n-1):
        fib.append(fib[-1] + fib[-2])
    return fib[-1]

Approach 3:

1
2
3
4
def climbStairs(self, n:int) -> int:
    phi = (1+sqrt(5))/2
    phi_ = (1-sqrt(5))/2
    return int(1/sqrt(5)*(phi**(n+1) - phi_**(n+1)))

Comments:

Time complexity for approach 1: O$\left(\frac{n}{2}T(math.comb)\right)$
Time complexity for approach 2: O(n)
Time complexity for approach 3: O(log n)

At the time of submission, the approach 1 passes leetcode submission cases in 33ms, beats 81.5% of users. It uses 17.26MB of memory, beating 31.07% of users.
At the time of submission, the above solution passes leetcode submission cases in 32ms, beats 84.91% of users. It uses 17.26MB of memory, beating 31.07% of users.
At the time of submission, the above solution passes leetcode submission cases in 30ms, beats 91.43% of users. It uses 17.15MB of memory, beating 45.94% of users.