Introduction to the Climbing Stairs Problem
The Climbing Stairs problem is one of the most classic algorithmic challenges you will encounter in coding interviews and competitive programming. It is a favorite among interviewers at companies like Amazon, Google, and Microsoft because it elegantly tests your understanding of dynamic programming, recursion, and optimization techniques.
The problem statement is deceptively simple: you are climbing a staircase that has n steps. You can climb either 1 or 2 steps at a time. The question is: how many distinct ways can you reach the top of the staircase?
In this tutorial, we will explore multiple approaches to solving this problem in JavaScript, starting from a naive recursive solution and progressively optimizing it until we reach an efficient, constant-space solution.
Understanding the Problem
Before jumping into code, let us build intuition. Suppose the staircase has 5 steps. At each point, you have two choices: take 1 step or take 2 steps. The total number of distinct ways is the sum of all possible sequences of 1s and 2s that add up to n.
Let us manually compute the answer for small values of n:
n = 1: Only 1 way → [1]n = 2: 2 ways → [1,1] or [2]n = 3: 3 ways → [1,1,1], [1,2], [2,1]n = 4: 5 ways → [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2]n = 5: 8 ways
Notice a pattern? The number of ways for n steps equals the sum of the ways for n-1 and n-2. This is the Fibonacci sequence in disguise. The reasoning is straightforward: to reach step n, your last move was either a 1-step from n-1 or a 2-step from n-2. Therefore, the total ways to reach n is ways(n-1) + ways(n-2).
Why This Problem Matters
The Climbing Stairs problem is more than an academic exercise. It teaches several fundamental concepts that apply broadly across software engineering:
- Dynamic Programming: It introduces the idea of breaking a problem into overlapping subproblems and storing intermediate results.
- Recursion and Memoization: It demonstrates how naive recursion can lead to exponential time complexity and how memoization fixes that.
- Space Optimization: It shows how to reduce an O(n) space solution to O(1) by recognizing that you only need the last two values.
- Pattern Recognition: Recognizing that a problem maps to the Fibonacci sequence is a valuable skill in algorithm design.
These skills transfer directly to real-world scenarios such as route planning, resource allocation, financial modeling, and any domain where you need to count combinations or optimize decisions over sequential steps.
Approach 1: Naive Recursion
The most intuitive solution is to translate the recurrence relation directly into a recursive function. If n is 1, there is 1 way. If n is 2, there are 2 ways. Otherwise, return the sum of the two previous values.
function climbStairsNaive(n) {
if (n === 1) return 1;
if (n === 2) return 2;
return climbStairsNaive(n - 1) + climbStairsNaive(n - 2);
}
console.log(climbStairsNaive(5)); // Output: 8
This solution is clean and readable, but it has a serious flaw. Its time complexity is O(2^n) because each call spawns two more calls, creating an exponential tree of repeated computations. For n = 40, this function will take a noticeable amount of time to complete, and for n = 50, it becomes practically unusable.
Approach 2: Recursion with Memoization
The naive recursion recomputes the same subproblems over and over. We can fix this by caching the results of each computation in a data structure. This technique is called memoization, and it reduces the time complexity to O(n) while keeping the recursive structure intact.
function climbStairsMemo(n, memo = {}) {
if (n === 1) return 1;
if (n === 2) return 2;
if (memo[n]) return memo[n];
memo[n] = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo);
return memo[n];
}
console.log(climbStairsMemo(50)); // Output: 20365011074
Now the function handles large values of n instantly. Each subproblem is computed only once, and subsequent lookups are O(1). The space complexity is O(n) for the memo object plus O(n) for the call stack.
Approach 3: Bottom-Up Dynamic Programming
We can eliminate recursion entirely by building the solution from the ground up. We create an array where each index i holds the number of ways to reach step i. We populate the array iteratively, starting from the base cases.
function climbStairsDP(n) {
if (n === 1) return 1;
if (n === 2) return 2;
const dp = new Array(n + 1);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
console.log(climbStairsDP(10)); // Output: 89
This approach runs in O(n) time and uses O(n) space. It is often preferred in interviews because iterative solutions avoid the risk of stack overflow that comes with deep recursion, especially in JavaScript engines that have limited call stack sizes.
Approach 4: Space-Optimized Solution
If you look closely at the bottom-up DP solution, you will notice that computing dp[i] only requires dp[i-1] and dp[i-2]. We do not need the entire array. We can replace it with two variables that we update as we iterate.
function climbStairs(n) {
if (n === 1) return 1;
if (n === 2) return 2;
let prev2 = 1; // ways to reach step 1
let prev1 = 2; // ways to reach step 2
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
console.log(climbStairs(45)); // Output: 1836311903
This is the optimal solution. It runs in O(n) time and uses only O(1) extra space. In most interviews, this is the answer the interviewer is looking for after guiding you through the earlier approaches.
Approach 5: Handling Large Inputs with BigInt
JavaScript numbers are represented as 64-bit floating-point values, which means they can safely represent integers only up to Number.MAX_SAFE_INTEGER (2^53 - 1). For very large values of n, the result will exceed this limit and lose precision. If you need exact results for large inputs, use BigInt.
function climbStairsBigInt(n) {
if (n === 1) return 1n;
if (n === 2) return 2n;
let prev2 = 1n;
let prev1 = 2n;
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
console.log(climbStairsBigInt(100).toString());
// Output: 573147844013817084101
Using BigInt ensures that you never lose precision, no matter how large n gets. The trade-off is that BigInt arithmetic is slightly slower than native number arithmetic, but for most practical purposes, the difference is negligible.
Best Practices
When solving the Climbing Stairs problem or similar dynamic programming challenges, keep the following best practices in mind:
- Start with the brute-force solution. Write the naive recursive approach first to confirm your understanding of the recurrence relation. Then optimize incrementally.
- Identify overlapping subproblems. If your recursive solution recomputes the same values repeatedly, memoization or tabulation will dramatically improve performance.
- Reduce space when possible. Always check whether you need the full DP table or just the last few values. Space optimization is a common follow-up question in interviews.
- Handle edge cases explicitly. Always account for
n = 0,n = 1, and negative inputs depending on the problem constraints. - Consider integer overflow. In JavaScript, be aware of
Number.MAX_SAFE_INTEGERand switch toBigIntwhen necessary. - Write tests. Verify your solution against known values for small inputs before trusting it with large ones.
Testing Your Solution
Here is a simple test suite you can use to validate your implementation across multiple approaches:
function testClimbStairs(fn, label) {
const testCases = [
{ input: 1, expected: 1 },
{ input: 2, expected: 2 },
{ input: 3, expected: 3 },
{ input: 4, expected: 5 },
{ input: 5, expected: 8 },
{ input: 10, expected: 89 },
{ input: 20, expected: 10946 },
];
let allPassed = true;
for (const { input, expected } of testCases) {
const result = fn(input);
const passed = result === expected;
if (!passed) allPassed = false;
console.log(
`${label}(${input}) = ${result} | Expected: ${expected} | ${passed ? "PASS" : "FAIL"}`
);
}
console.log(allPassed ? "All tests passed!\n" : "Some tests failed.\n");
}
testClimbStairs(climbStairs, "Space-Optimized");
testClimbStairs(climbStairsDP, "Bottom-Up DP");
testClimbStairs(climbStairsMemo, "Memoized");
Running these tests ensures that all your implementations produce consistent and correct results. If any approach fails a test case, you have a clear signal to debug that specific implementation.
Variations of the Problem
Once you master the basic Climbing Stairs problem, try these variations to deepen your understanding:
- Variable step sizes: Instead of only 1 or 2 steps, allow a set of step sizes like [1, 3, 5]. The recurrence becomes the sum of
ways(n - step)for each allowed step size. - Cost minimization: Each step has a cost. Find the minimum cost to reach the top, where you can start from step 0 or step 1.
- Obstacle avoidance: Some steps are blocked. Modify the recurrence to skip paths that land on a blocked step.
- Three steps at a time: Allow climbing 1, 2, or 3 steps. The recurrence becomes a tribonacci sequence.
Each variation forces you to re-examine the recurrence relation and adjust your DP state accordingly. Practicing these will make you more adaptable when facing unfamiliar dynamic programming problems.
Conclusion
The Climbing Stairs problem is a gateway into the world of dynamic programming. By working through the naive recursive solution, adding memoization, building a bottom-up DP table, and finally optimizing space to O(1), you develop a repeatable framework for tackling a wide range of algorithmic challenges. The key takeaway is that recognizing patterns, identifying overlapping subproblems, and iteratively refining your solution are skills that extend far beyond this single problem. Whether you are preparing for a coding interview or simply sharpening your problem-solving abilities, mastering this problem in JavaScript gives you a solid foundation for approaching more complex dynamic programming scenarios with confidence.