Leetcode Climbing Stairs Solution (Python)

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?

Constraints:

1 <= n <= 45

Solution (Python)

class Solution:
    # dp[i] denotes number of ways for stairs with i steps
    dp = [-1 for i in range(45+1)]
        
    def climbStairs(self, n: int) -> int:
        # Base case
        if n<=1:
            return 1
        if self.dp[n]!=-1:
            return self.dp[n]
        # Recursive step
        self.dp[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
        return self.dp[n]