LeetCode 70: Climbing Stairs — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Easy — Dynamic Programming | Math | Fibonacci

The Problem

Given n stairs, find the number of distinct ways to climb to the top where you can climb either 1 or 2 steps at a time.

Approach

Use dynamic programming with space optimization by recognizing this follows the Fibonacci sequence pattern. Store only the previous two values instead of the entire array, as each step depends only on the two preceding steps.

Time: O(n) · Space: O(1)

Code

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

        prev1 = 1  # Number of ways to reach the 1st stair
        prev2 = 2  # Number of ways to reach the 2nd stair

        for i in range(3, n + 1):
            current = prev1 + prev2
            prev1, prev2 = prev2, current  # Update for the next iteration

        return prev2  # Number of ways to reach the n-th stair