Climbing Stairs (Leetcode 70)

Problem Link: https://leetcode.com/problems/climbing-stairs/

Recursion + Memoization

class Solution:
    def climbStairs(self, n: int) -> int:
        
        # Recursion + Memoization
        
        def recursion(n,dp):
            if(n==0):
                return 1
            elif(n<0):
                return 0
            
            if(dp[n]!=-1):
                return dp[n]
            f=recursion(n-1,dp)
            s=recursion(n-2,dp)
            dp[n]=f+s
            return dp[n]

                 
        dp=[-1]*(n+1)
        return recursion(n,dp)

Tabulation

class Solution:
    def climbStairs(self, n: int) -> int:
        
        # Tabulation
        dp=[-1]*(n+1)
        dp[0]=1
        dp[1]=1
        for i in range(2,n+1):
            dp[i]=dp[i-1]+dp[i-2]
        return dp[n]