Skip to content

70. Climbing Stairs

Summary

Solution Approach Explanation (1-minute) Time Complexity Space Complexity
Dynamic Programming Count ways to reach each step by adding ways from the previous two steps. Like Fibonacci - each number is sum of previous two. \(O(n)\) \(O(n)\)

Implementation

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = []
        for i in range(n):
            if i==0:
                dp.append(1)
            elif i==1:
                dp.append(2)
            else:
                dp.append(dp[i-2] + dp[i-1])
        return dp[-1]