Climbing Stairs
EasyPrompt
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 stepsExample 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Constraints:
1 <= n <= 45
Approaches
5 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's recurrence relation, ways(n) = ways(n-1) + ways(n-2), into a recursive function. It's the most straightforward way to think about the problem but is highly inefficient.
Algorithm
- Define a function
climbStairs(n). - Handle the base cases: if
nis 1, return 1; ifnis 2, return 2. - For other values of
n, make a recursive call:return climbStairs(n - 1) + climbStairs(n - 2);.
Walkthrough
The core idea is that to reach the n-th step, you must have come from either the (n-1)-th step (by taking one step) or the (n-2)-th step (by taking two steps). The total number of ways is the sum of the ways to reach these two preceding steps. We define a function climbStairs(n) that calls itself for n-1 and n-2 and sums their results. The base cases are for n=1 (1 way) and n=2 (2 ways). This creates a large recursion tree where the number of ways for the same step is calculated multiple times, leading to an exponential time complexity.
public class Solution { public int climbStairs(int n) { if (n <= 0) { return 0; } if (n == 1) { return 1; } if (n == 2) { return 2; } return climbStairs(n - 1) + climbStairs(n - 2); }}Complexity
Time
O(2^n)
Space
O(n)
Trade-offs
Pros
Simple to write and understand as it directly models the problem's definition.
Cons
Extremely inefficient due to re-computation of the same subproblems.
Will result in a 'Time Limit Exceeded' error for moderately large values of
n(e.g., n > 35).
This approach, also known as top-down dynamic programming, improves upon the brute-force recursion by storing the results of subproblems in a cache (the memoization table). This avoids redundant calculations for the same step, significantly improving performance.
Algorithm
- Create a memoization array
memoof sizen + 1to store computed results. - Define a helper function, say
climb(n, memo). - In the helper function, handle base cases: if
n <= 2, returnn. - Before computing, check if
memo[n]has a stored result. If yes, return it. - If not, compute the result recursively:
memo[n] = climb(n - 1, memo) + climb(n - 2, memo). - Store the result in
memo[n]and return it.
Walkthrough
We observe that the brute-force approach recomputes the number of ways for the same step multiple times. To optimize this, we use an array, memo, to store the result for each step i once it's computed. Before computing climbStairs(i), we first check if memo[i] has already been calculated. If it has, we return the stored value. If not, we compute it recursively, store the result in memo[i], and then return it. This ensures that each subproblem is solved only once.
public class Solution { public int climbStairs(int n) { int[] memo = new int[n + 1]; return climb(n, memo); } private int climb(int n, int[] memo) { if (n <= 2) { return n; } if (memo[n] > 0) { return memo[n]; } memo[n] = climb(n - 1, memo) + climb(n - 2, memo); return memo[n]; }}Complexity
Time
O(n)
Space
O(n)
Trade-offs
Pros
Drastically more efficient than brute-force, with linear time complexity.
Maintains the logical structure of the recursive solution.
Cons
Requires extra space for the memoization array.
Incurs the overhead of recursive function calls.
This approach, also known as bottom-up dynamic programming, solves the problem iteratively. It builds the solution from the base cases up to the desired step n, avoiding recursion entirely.
Algorithm
- If
n <= 2, returnn. - Create a DP array
dpof sizen + 1. - Initialize the base cases:
dp[1] = 1,dp[2] = 2. - Loop from
i = 3ton. - In the loop, calculate
dp[i] = dp[i - 1] + dp[i - 2]. - After the loop, return
dp[n].
Walkthrough
We can recognize that climbStairs(n) is the n-th number in a Fibonacci-like sequence. We can build this sequence from the bottom up. We create a DP array, dp, of size n + 1, where dp[i] will store the number of ways to reach the i-th step. We initialize the base cases dp[1] = 1 and dp[2] = 2. Then, we iterate from i = 3 to n, filling the dp array using the same recurrence relation: dp[i] = dp[i-1] + dp[i-2]. The final answer is the value stored in dp[n].
public class Solution { public int climbStairs(int n) { if (n <= 2) { return n; } int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }}Complexity
Time
O(n)
Space
O(n)
Trade-offs
Pros
Efficient with linear time complexity.
Avoids recursion overhead, which can be slightly faster than memoization in practice.
Cons
Uses O(n) space for the DP array, which is not optimal.
This approach optimizes the bottom-up DP solution by reducing the space complexity from O(n) to O(1). It's one of the most common and efficient solutions for this problem.
Algorithm
- Handle base cases: if
n <= 2, returnn. - Initialize two variables:
two_steps_back = 1(forn=1) andone_step_back = 2(forn=2). - Loop from
i = 3ton. - Inside the loop, calculate
current_ways = one_step_back + two_steps_back. - Update the variables:
two_steps_back = one_step_backandone_step_back = current_ways. - After the loop, return
one_step_back.
Walkthrough
When calculating the number of ways for the current step i, we only need the results for the previous two steps, i-1 and i-2. There is no need to store the entire DP array. We can use just two variables to keep track of the last two values. Let's use one_step_back to store the ways for step i-1 and two_steps_back for step i-2. We iterate from 3 to n, and in each step, we calculate the current number of ways by summing one_step_back and two_steps_back. Then we update our pointers: two_steps_back becomes the old one_step_back, and one_step_back becomes the current value.
public class Solution { public int climbStairs(int n) { if (n <= 2) { return n; } int two_steps_back = 1; int one_step_back = 2; for (int i = 3; i <= n; i++) { int current_ways = one_step_back + two_steps_back; two_steps_back = one_step_back; one_step_back = current_ways; } return one_step_back; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Highly efficient in both time and space.
Optimal for typical interview constraints.
Cons
The logic might be slightly less direct to understand compared to the DP array approach.
This is a mathematical approach that uses a closed-form formula to calculate the n-th Fibonacci number directly. It is the most time-efficient approach, with logarithmic time complexity.
Algorithm
- Calculate
sqrt5 = Math.sqrt(5). - Calculate the golden ratio
phi = (1 + sqrt5) / 2. - Calculate
phiraised to the power ofn + 1usingMath.pow(phi, n + 1). - Divide the result by
sqrt5. - Round the final result to the nearest integer and cast it to
int.
Walkthrough
The number of ways to climb n stairs corresponds to the (n+1)-th Fibonacci number (F_{n+1}), where the sequence starts F_1=1, F_2=1, .... Binet's formula provides a direct way to calculate the k-th Fibonacci number: F_k = (φ^k - ψ^k) / √5, where φ = (1 + √5) / 2 is the golden ratio. Since the second term in the numerator is very small, the formula can be simplified to finding the nearest integer to φ^k / √5. We need to calculate the result for k = n + 1. The Math.pow(base, exp) function typically has a time complexity of O(log exp), making this approach extremely fast.
public class Solution { public int climbStairs(int n) { double sqrt5 = Math.sqrt(5); double phi = (1 + sqrt5) / 2; double result = Math.pow(phi, n + 1) / sqrt5; return (int) Math.round(result); }}Complexity
Time
O(log n)
Space
O(1)
Trade-offs
Pros
The most time-efficient approach.
Constant space complexity.
Cons
Relies on floating-point arithmetic, which can have precision issues for very large numbers (though not an issue for
n <= 45).Less intuitive and harder to derive during an interview if not already known.
Solutions
Solution
class Solution {public int climbStairs(int n) { int a = 0, b = 1; for (int i = 0; i < n; ++i) { int c = a + b; a = b; b = c; } return b; }}/** * @param {number} n * @return {number} */ var climbStairs = function (n) { let a = 0, b = 1; for (let i = 0; i < n; ++i) { const c = a + b; a = b; b = c; } return b;};class Solution {public: int climbStairs(int n) { int a = 0, b = 1; for (int i = 0; i < n; ++i) { int c = a + b; a = b; b = c; } return b; }};class Solution: def climbStairs(self, n: int) -> int: a, b = 0, 1 for _ in range(n): a, b = b, a + b return bVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.