Climbing Stairs#

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?

Fibonacci Pattern#

  • This is a permutation pattern in-comparison to coin change problem 2(takes only combination) Example: Input: n = 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

  • Both 2 & 3 permutation are possible - if the question is about no of ways to reach, then go for permutation

Handling base case#

def fib(n):
    if n == 0: return 1
    if n == 1: return 1
    if n == 2: return 2
    pass

fib(1)

1

fib(10)

Recursion#

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0: return 1
        if n == 1: return 1
        if n == 2: return 2

        return self.climbStairs(n-1) + self.climbStairs(n-2)

x= Solution()

x.climbStairs(5)

8

Recursion with memoization#

class Solution:
    def climbStairs(self, n: int) -> int:
        mem = {}
        def climb(n):
            if n == 0: return 1
            if n == 1: return 1
            if n == 2: return 2
            if n in mem:
                return mem[n]
            mem[n] = climb(n-1) + climb(n-2)
            return mem[n]
        return climb(n)

x = Solution()
x.climbStairs(5)

8

DP Solution#

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

x = Solution()
x.climbStairs(5)

8