70. Climbing Stairs

At a Glance

• Topic: dp-1d
• Pattern: Dynamic Programming (Fibonacci-style linear recurrence)
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Bloomberg, Adobe
• Frequency: Very High
• LeetCode: 70

Problem (one-liner)

You can climb 1 or 2 steps at a time. Given n stairs, count how many distinct ways reach the top (order matters). Input: integer n. Output: number of ways.

Recognition Cues

• "Climb 1 or 2 steps"
• "Number of distinct ways" / "how many ways"
• Same recurrence as Fibonacci with base cases ways(1)=1, ways(2)=2

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — O(2^n) time / O(n) stack — recurse without memo (exponential).
• Better — top-down DP with memo — O(n) time / O(n) space.
• Optimal — bottom-up with rolling state — O(n) time / O(1) space. <- pick this in interview.

Optimal Solution

Go

package main

func climbStairsTable(n int) int {
	if n <= 2 {
		return n
	}
	dp := make([]int, n+1)
	dp[1] = 1
	dp[2] = 2
	for step := 3; step <= n; step++ {
		dp[step] = dp[step-1] + dp[step-2]
	}
	return dp[n]
}

func climbStairs(n int) int {
	if n <= 2 {
		return n
	}
	previous := 1
	current := 2
	for step := 3; step <= n; step++ {
		next := previous + current
		previous = current
		current = next
	}
	return current
}

JavaScript

function climbStairsTable(n) {
	if (n <= 2) return n;
	const dp = new Array(n + 1).fill(0);
	dp[1] = 1;
	dp[2] = 2;
	for (let step = 3; step <= n; step++) {
		dp[step] = dp[step - 1] + dp[step - 2];
	}
	return dp[n];
}

function climbStairs(n) {
	if (n <= 2) return n;
	let previous = 1;
	let current = 2;
	for (let step = 3; step <= n; step++) {
		const next = previous + current;
		previous = current;
		current = next;
	}
	return current;
}

Walkthrough

Input: n = 5

Invariant: dp[k] counts ways to reach step k from the ground; only last two values matter for O(1) space.

Edge Cases

• n = 1 returns 1
• n = 2 returns 2
• Large n fits in 32-bit for problem constraints

Pitfalls

• Off-by-one on base cases (n=1 vs n=2)
• Using float math or closed-form without integer care
• Forgetting the rolling optimization is valid because recurrence is order-2

Similar Problems

• 746. Min Cost Climbing Stairs — same step model with costs.
• 198. House Robber — linear “take or skip” DP on a path.
• 322. Coin Change — unbounded steps with value—another linear DP family.

Variants

• Costs per step → min cost path (see Min Cost Climbing Stairs).
• Steps in {1,2,3} → tribonacci-style rolling window of width 3.

Mind-Map Tags

#dp-1d #linear-dp #fibonacci #rolling-state #easy