Climbing Stairs | LeetCode | Solution Explained

70. Climbing Stairs is an easy LeetCode problem. We first look at the iterative dynamic programming (dp) approach followed by the more simpler constant space approach. I explain how we can think about this problem in terms of the classic Fibonacci problem.

Iterative DP

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0]*(n+1)
        
        dp[0] = dp[1] = 1
        for i in range(2, n+1):
            dp[i] = dp[i-1]+dp[i-2]
        
        return dp[n]
  • Time: O(N)
  • Space: O(N)

Space Optimizations

We only look at the last two values for computing ith value. Instead of an array, we can just keep ‘a’ and ‘b’ variables to compute ‘c’.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2: return n
        a = 1
        b = 1
        c = a + b
        for _ in range(n-2): # n-2 because first two have already been completed
            a = b
            b = c
            c = a + b

        return c
Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.