Climbing Stairs
LeetCode 70 • Easy • Dynamic Programming
Climb to step n. Each step: either 1 or 2 stairs. ways[0]=1, ways[1]=1, ways[i]=ways[i-1]+ways[i-2]. O(1) space with prev
and curr.
TimeO(n)single pass
SpaceO(1)prev, curr
prev: —
curr: —
Ready
Press Play. For each step i: curr = prev + curr; prev = old curr. O(1) space.
TimeO(n)memoized
SpaceO(n)memo + call stack
Recursive: climb(n) — base n≤1 return 1; if n in memo return memo[n]; memo[n] = climb(n-1) + climb(n-2); return memo[n].
Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.
# ─── CLIMBING STAIRS (LeetCode 70) ───
# Pattern: Fibonacci DP (O(1) space)
# Time: O(n) Space: O(1)
#
# 1. Define: climbStairs(n)
#
# 2. Base case:
# if n <= 1: return 1
#
# 3. Init prev, curr (ways for step 0 and 1):
# prev, curr = 1, 1
#
# 4. Loop from step 2 to n:
# for i in range(2, n + 1):
#
# 5. Roll forward: prev, curr = curr, prev + curr
#
# 6. Return: return curr
#
# Vars: prev, curr, i
▼ your implementation ▼
Verify your solution: