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

Watch It Run

👁 Watch the algorithm run step by step

👁 Watch the algorithm run step by step

Open interactive visualization

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.