Suggest solution: Fibonacci Numbers


  • 2
    Z

    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]

  • 1
    R

    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]

  • 0
    Z

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


  • 0
    R

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


  • 0
    W

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


Log in to reply
 

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