70. Climbing Stairs

Approach: DP (O(n) Space)

Let dp[i] represents the number of ways to climb the stairs.

The recurrence relation is: dp[i] = dp[i-1] + dp[i-2]

Similar to the fibonacci problem, to reach step i:

• Come from step i-1 with a 1-step move
• Come from step i-2 with a 2-step move

So the number of ways to reach step n is the sum of the ways to reach steps i-1 and i-2.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        dp = [0] * (n+1)
        dp[1], dp[2] = 1, 2

        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]

• Time: $O(n)$ — we iterate through the array once.
• Space: $O(n)$ — we use an array of size $n+1$ to store the intermediate results.

Last updated on