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

    Leave a Reply

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