Climbing Stairs

Question

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

1 <= n <= 45

Solution

• Thoughts

1. Calculate ways by including different 2s. i.e. If only climb 2 steps once, the ways is \(C_1^{n-1}\). And if climb 2 steps twice, the ways is \(C_2^{n-2}\). So we can generalize the ways to \(C_k^{n-k}\) (\(n-k \geq k\)).

2. Add them together.

• Code

def climbStairs(n):

  if n < 1 or n > 45:
    print("Out of range")
  else:
    # step 1 calculate combination
    def cnk(m, k):
      if k == 1:
        res = m
      if m == k:
        res = 1
      else:
        res = m/(m-k) * cnk(m-1, m-k-1)
      return res
      
    # step 2 add them together
    res = k = 1
    while k <= (n - k):
      res += cnk(n - k, k)
      k += 1
    return int(res)
    

for i in range(0, 47):
  climbStairs(i)

## Out of range
## 1
## 2
## 3
## 5
## 8
## 13
## 21
## 34
## 55
## 89
## 144
## 233
## 377
## 610
## 987
## 1597
## 2584
## 4181
## 6765
## 10946
## 17711
## 28657
## 46367
## 75025
## 121393
## 196417
## 317811
## 514229
## 832040
## 1346269
## 2178309
## 3524577
## 5702887
## 9227465
## 14930352
## 24157817
## 39088169
## 63245986
## 102334155
## 165580141
## 267914296
## 433494437
## 701408733
## 1134903170
## 1836311903
## Out of range

Summary

It turns out the answer is just Fibonacci Sequence! But how to think about it?

The last clime is either 1 step or 2 steps. So we seperate it to two categoricals. For the first one there is ways(n - 1), and ways(n-2) for latter one.

Therefore, ways(n) = ways(n - 1) + ways(n-2)

Programming is much easier.

def climbStairs2(n):
  a, b = 1, 1
  for i in range(n):
    a, b = b, a+b
  return a

for i in range(1, 10):
  climbStairs2(i)  

## 1
## 2
## 3
## 5
## 8
## 13
## 21
## 34
## 55