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.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

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

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

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