Climbing Stairs

Problem Summary

• How many ways you can reach $n$ number of steps if at each level you can do 1 step or 2 step

Key Observations

• Similar to Fibonacci

Approach Taken

• Build a decision tree
• At each node you can go two routes $n-1$ or $n-2$

Main Concepts Used

• Recursion
• Dynamic Programming
• Memoization

Time & Space Complexity

• Time: $O(n)$ → Reason: Storing sub-calls of counting $n-1$ and $n-2$
• Space: $O(n)$ → Reason: Recursion stack

Code

class Solution:
    def climbStairs(self, n: int) -> int:
        result = 0
        memo = {0: 1, -1: 0}

        def helper(left):
            if left in memo:
                return memo[left]

            memo[left - 1] = helper(left - 1)
            memo[left - 2] = helper(left - 2)
            return memo[left - 1] + memo[left - 2]

        return helper(n)

Optimized DP

• Space complexity of $O(n)$ can be improved to $O(1)$
• We know our base case when we reach the target is 1
• 

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[n] = 1
        for i in range(n - 1, -1, -1):
            oneStep = dp[i + 1] if i + 1 <= n else 0
            twoStep = dp[i + 2] if i + 2 <= n else 0
            dp[i] = oneStep + twoStep

        return dp[0]