Abstract / Summary

You can climb a staircase by taking one or two steps at a time and need to find how many ways to reach the top.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 54% (9+ million submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Math
• Memoization

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The presented implementation solves the classic combinatorial problem of counting distinct ways to ascend a staircase when each step can be either a single or a double stride. The solution employs a depth-first recursion augmented with memoization to avoid redundant sub-problem evaluations. The public interface climbStairs prepares the memoization structure and initiates the recursive exploration from the ground level.

Core Logic

At the heart of the algorithm lies the recursive helper dp. It receives two parameters: current, the index of the step currently occupied, and total, the target step count. The function first checks whether the traversal has overshot the destination; in that case it returns zero, indicating an invalid path. When the exact target is reached, it returns one, signifying a successful way to climb the stairs.

int dp(int current, int total)
{
    if (current > total)
        return 0;
    if (current == total)
        return 1;
    // ...
}

If the result for the current position has already been computed, the cached value is returned immediately, preventing duplicate work. Otherwise the function explores the two permissible moves: advancing by one step and by two steps. The results of these two recursive calls are summed to produce the total number of ways from the current position, stored in the cache, and then returned.

if (cache[current] >= 0)
    return cache[current];

int one = dp(current + 1, total);
int two = dp(current + 2, total);
int result = one + two;

cache[current] = result;
return result;

Memoization Strategy

The memoization container cache is a vector<int> that holds pre-computed results for each possible step index. Before any recursion begins, climbStairs clears any existing content and resizes the vector to a fixed capacity of 50 elements, initializing each entry to -1 to denote an uncomputed state. This size comfortably exceeds typical input ranges for the problem while keeping memory usage predictable.

int climbStairs(int n) {
    cache.clear();
    cache.resize(50, -1);
    return dp(0, n);
}

By indexing directly with the current step, the algorithm achieves constant-time access to previously solved sub-problems, which dramatically reduces the exponential blow-up inherent in naïve recursion.

Edge Cases Handled

The implementation explicitly addresses the scenario where the recursion steps beyond the target (current > total). Returning zero in this branch ensures that overshooting paths do not contribute to the final count. The exact match case (current == total) returns one, correctly counting the scenario where the staircase has been climbed precisely. These two base conditions together guarantee that all possible traversal paths are evaluated accurately, including the minimal input where n equals zero (the function will return one, representing the empty sequence of moves).

Performance Optimizations

The primary optimization stems from the memoization cache, which transforms the recursive exploration from an exponential to a linear number of distinct sub-problem evaluations. By storing each intermediate result after its first computation, subsequent calls for the same current index bypass the recursive descent entirely. The fixed cache size eliminates the overhead of dynamic resizing during recursion, and the use of a simple integer vector ensures low-level memory locality, which benefits CPU cache performance. Additionally, the early return checks for out-of-bounds and exact matches prevent unnecessary recursive calls, further trimming the execution path.

Imagine there is a tall staircase with many steps, and there is a little person who wants to get to the very top. To climb the stairs, this person can either jump up one step at a time or take a big leap of two steps at once. The code is like a clever helper that counts all the different ways to reach the top. It starts at the bottom and keeps track of every choice made, like choosing a tiny step or a big jump.

Because there are so many ways to climb, it could take a very long time to count them one by one. To stay fast, the helper keeps a special notebook called a cache. Whenever the helper figures out how many ways there are to finish the climb from a certain step, that number gets written down in the notebook. If the helper ever needs to know that same information again, it just peeks at the notebook instead of doing all the hard work over again.

The main part of the code gets everything ready by clearing the notebook and giving it plenty of space to remember things. Then, it sends the helper off to start at the bottom step and climb all the way to the end. The helper follows the simple rule of trying both the one-step and two-step moves, writing down the answers as it goes, until every path to the top is counted.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java			Rust	JS	Go	TS			PHP
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei						Rust
	begeekmyfriend				C
	BigEggStudy					C#
	black-shadows	C++
	bujosa		Python
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	DimitrisJim				C
	everthis							JS
	fartem										Ruby
	FelixFan1122					C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost								Go
	JoshCrozier							JS
	keineahnung2345	C++
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	luangong	C++								TS
	MacJim	C++
	muhammadfarhankt								Go
	pruthvikp		Python
	qiyuangong		Python
	ruoru						Rust
	shreymehul					C#
	sonugiri1043	C++
	suxrobGM			Java
	varunu28			Java
	vli02				C
	vthwang			Java
	XiaotaoGuo	C++
	yuanliu666											Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++, TypeScript
MacJim	C++
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	Java
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality