# Suggest solution: Fibonacci Numbers

• The number of distinct ways is the Fibonacci Numbers, since when you climb the n stairs, you need distinct ways of n-1(1 more steps here) stairs plus distinct ways of n-2 stairs (2 more steps here). For example, when you climb 4 stairs, you can either climb 3 stairs (3 ways) and 1 more step or 2 sitars (2 ways) and 2 more steps, so there are 5 ways in total. So the solution becomes easy, here is a non- recursive one:

``````def climbStairs(self, n):
fib = {}
f=0
for i in range (1,n+1):
if i <= 2:
f = i
else:
f = fib[i-1] + fib[i-2]
fib[i] = f
return fib[n]``````

• Python Solution

``````class Solution:
# @param n, an integer
# @return an integer
def climbStairs(self, n):
if n==0 or n==1 or n==2:
return n
num=[1,2]
for i in range(2,n):
num.append(num[i-2]+num[i-1])
return num[n-1]``````

• Nice, Reeclapple! Append is my favorite method, but I'm not sure if interviewers would prefer hash tables, recursive, or others

• For this question DP shall be the best solution. Recursion would definitely took extra overhead.

• thank you! your explanation makes so much more sense than everyone jumping to fibonacci.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.