Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
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?
Input:
- An integer n representing the number of steps (1 ≤ n ≤ 45)
Output:
- Number of distinct ways to climb to the top
Constraints:
- 1 ≤ n ≤ 45
Examples:
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top:
1. 1 step + 1 step
2. 2 steps
Example 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
Example 3:
Input: n = 4
Output: 5
Explanation: There are five ways to climb to the top:
1. 1+1+1+1
2. 2+1+1
3. 1+2+1
4. 1+1+2
5. 2+2
Solutions
Approach 1: Recursive Solution (Naive)
The problem follows the same pattern as Fibonacci numbers since to reach step n, you can either come from step (n-1) with a 1-step or from step (n-2) with a 2-step.
Algorithm:
- Base cases: ways(1) = 1, ways(2) = 2
- For n > 2: ways(n) = ways(n-1) + ways(n-2)
Python:
def climbStairs_recursive(n):
"""
Naive recursive solution
Time: O(2^N) - exponential due to repeated calculations
Space: O(N) - recursion call stack
"""
if n <= 2:
return n
return climbStairs_recursive(n - 1) + climbStairs_recursive(n - 2)
# Example usage
print(climbStairs_recursive(5)) # Output: 8
Java:
class Solution {
/**
* Naive recursive solution
* Time: O(2^N)
* Space: O(N)
*/
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
}
Go:
// climbStairsRecursive - Naive recursive solution
// Time: O(2^N)
// Space: O(N)
func climbStairsRecursive(n int) int {
if n <= 2 {
return n
}
return climbStairsRecursive(n-1) + climbStairsRecursive(n-2)
}
JavaScript:
/**
* Naive recursive solution
* Time: O(2^N)
* Space: O(N)
*/
function climbStairsRecursive(n) {
if (n <= 2) {
return n;
}
return climbStairsRecursive(n - 1) + climbStairsRecursive(n - 2);
}
C#:
public class Solution {
/// <summary>
/// Naive recursive solution
/// Time: O(2^N)
/// Space: O(N)
/// </summary>
public int ClimbStairs(int n) {
if (n <= 2) {
return n;
}
return ClimbStairs(n - 1) + ClimbStairs(n - 2);
}
}
Approach 2: Memoization (Top-Down DP)
Optimize the recursive solution by caching previously computed results.
Python:
def climbStairs_memoization(n, memo=None):
"""
Top-down DP with memoization
Time: O(N) - each subproblem computed once
Space: O(N) - memoization table + recursion stack
"""
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 2:
return n
memo[n] = climbStairs_memoization(n - 1, memo) + climbStairs_memoization(n - 2, memo)
return memo[n]
def climbStairs_lru_cache(n):
"""
Using functools.lru_cache decorator
Time: O(N)
Space: O(N)
"""
from functools import lru_cache
@lru_cache(maxsize=None)
def climb(n):
if n <= 2:
return n
return climb(n - 1) + climb(n - 2)
return climb(n)
# Example usage
print(climbStairs_memoization(10)) # Output: 89
Java:
import java.util.HashMap;
import java.util.Map;
class Solution {
private Map<Integer, Integer> memo = new HashMap<>();
/**
* Top-down DP with memoization
* Time: O(N)
* Space: O(N)
*/
public int climbStairs(int n) {
if (memo.containsKey(n)) {
return memo.get(n);
}
if (n <= 2) {
return n;
}
int result = climbStairs(n - 1) + climbStairs(n - 2);
memo.put(n, result);
return result;
}
/**
* Alternative with explicit memo parameter
* Time: O(N)
* Space: O(N)
*/
public int climbStairsWithMemo(int n) {
Map<Integer, Integer> memo = new HashMap<>();
return climbStairsHelper(n, memo);
}
private int climbStairsHelper(int n, Map<Integer, Integer> memo) {
if (memo.containsKey(n)) {
return memo.get(n);
}
if (n <= 2) {
return n;
}
int result = climbStairsHelper(n - 1, memo) + climbStairsHelper(n - 2, memo);
memo.put(n, result);
return result;
}
}
Go:
// climbStairsMemoization - Top-down DP with memoization
// Time: O(N)
// Space: O(N)
func climbStairsMemoization(n int) int {
memo := make(map[int]int)
return climbStairsHelper(n, memo)
}
func climbStairsHelper(n int, memo map[int]int) int {
if val, exists := memo[n]; exists {
return val
}
if n <= 2 {
return n
}
result := climbStairsHelper(n-1, memo) + climbStairsHelper(n-2, memo)
memo[n] = result
return result
}
JavaScript:
/**
* Top-down DP with memoization
* Time: O(N)
* Space: O(N)
*/
function climbStairsMemoization(n, memo = {}) {
if (n in memo) {
return memo[n];
}
if (n <= 2) {
return n;
}
memo[n] = climbStairsMemoization(n - 1, memo) + climbStairsMemoization(n - 2, memo);
return memo[n];
}
/**
* Using Map for memoization
* Time: O(N)
* Space: O(N)
*/
function climbStairsMemoMap(n) {
const memo = new Map();
function climb(n) {
if (memo.has(n)) {
return memo.get(n);
}
if (n <= 2) {
return n;
}
const result = climb(n - 1) + climb(n - 2);
memo.set(n, result);
return result;
}
return climb(n);
}
C#:
using System.Collections.Generic;
public class Solution {
private Dictionary<int, int> memo = new Dictionary<int, int>();
/// <summary>
/// Top-down DP with memoization
/// Time: O(N)
/// Space: O(N)
/// </summary>
public int ClimbStairs(int n) {
if (memo.ContainsKey(n)) {
return memo[n];
}
if (n <= 2) {
return n;
}
int result = ClimbStairs(n - 1) + ClimbStairs(n - 2);
memo[n] = result;
return result;
}
}
Approach 3: Tabulation (Bottom-Up DP)
Build the solution iteratively from the bottom up.
Python:
def climbStairs_tabulation(n):
"""
Bottom-up DP with tabulation
Time: O(N) - single pass through numbers
Space: O(N) - DP table
"""
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Example usage
print(climbStairs_tabulation(10)) # Output: 89
Java:
class Solution {
/**
* Bottom-up DP with tabulation
* Time: O(N)
* Space: O(N)
*/
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];
}
}
Go:
// climbStairsTabulation - Bottom-up DP with tabulation
// Time: O(N)
// Space: O(N)
func climbStairsTabulation(n int) int {
if n <= 2 {
return n
}
dp := make([]int, n+1)
dp[1] = 1
dp[2] = 2
for i := 3; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
JavaScript:
/**
* Bottom-up DP with tabulation
* Time: O(N)
* Space: O(N)
*/
function climbStairsTabulation(n) {
if (n <= 2) {
return n;
}
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];
}
C#:
public class Solution {
/// <summary>
/// Bottom-up DP with tabulation
/// Time: O(N)
/// Space: O(N)
/// </summary>
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];
}
}
Approach 4: Space Optimized DP
Since we only need the last two values, optimize space to O(1).
Python:
def climbStairs_optimized(n):
"""
Space-optimized DP solution
Time: O(N) - single pass
Space: O(1) - only storing two variables
"""
if n <= 2:
return n
prev2 = 1 # ways(1)
prev1 = 2 # ways(2)
for i in range(3, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
def climbStairs_pythonic(n):
"""
Pythonic space-optimized solution
Time: O(N)
Space: O(1)
"""
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b
# Example usage
print(climbStairs_optimized(10)) # Output: 89
Java:
class Solution {
/**
* Space-optimized DP solution
* Time: O(N)
* Space: O(1)
*/
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int prev2 = 1; // ways(1)
int prev1 = 2; // ways(2)
for (int i = 3; i <= n; i++) {
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
Go:
// climbStairsOptimized - Space-optimized DP solution
// Time: O(N)
// Space: O(1)
func climbStairsOptimized(n int) int {
if n <= 2 {
return n
}
prev2, prev1 := 1, 2 // ways(1), ways(2)
for i := 3; i <= n; i++ {
current := prev1 + prev2
prev2 = prev1
prev1 = current
}
return prev1
}
// Alternative with multiple assignment
func climbStairsOptimizedAlt(n int) int {
if n <= 2 {
return n
}
a, b := 1, 2
for i := 3; i <= n; i++ {
a, b = b, a+b
}
return b
}
JavaScript:
/**
* Space-optimized DP solution
* Time: O(N)
* Space: O(1)
*/
function climbStairsOptimized(n) {
if (n <= 2) {
return n;
}
let prev2 = 1; // ways(1)
let prev1 = 2; // ways(2)
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
/**
* Using destructuring assignment
* Time: O(N)
* Space: O(1)
*/
function climbStairsDestructuring(n) {
if (n <= 2) {
return n;
}
let [a, b] = [1, 2];
for (let i = 3; i <= n; i++) {
[a, b] = [b, a + b];
}
return b;
}
C#:
public class Solution {
/// <summary>
/// Space-optimized DP solution
/// Time: O(N)
/// Space: O(1)
/// </summary>
public int ClimbStairs(int n) {
if (n <= 2) {
return n;
}
int prev2 = 1; // ways(1)
int prev1 = 2; // ways(2)
for (int i = 3; i <= n; i++) {
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
/// <summary>
/// Using tuple for swapping
/// Time: O(N)
/// Space: O(1)
/// </summary>
public int ClimbStairsTuple(int n) {
if (n <= 2) {
return n;
}
(int a, int b) = (1, 2);
for (int i = 3; i <= n; i++) {
(a, b) = (b, a + b);
}
return b;
}
}
Approach 5: Mathematical Formula (Binets’ Formula)
Using the mathematical relationship with Fibonacci numbers and the golden ratio.
Python:
def climbStairs_formula(n):
"""
Mathematical approach using Binet's formula
Time: O(1) - constant time calculation
Space: O(1) - no extra space
Note: May have precision issues for large n
"""
import math
# Golden ratio
phi = (1 + math.sqrt(5)) / 2
psi = (1 - math.sqrt(5)) / 2
# Binet's formula adapted for climbing stairs
# stairs(n) = fib(n+1) where fib uses 0-indexing
return int((phi ** (n + 1) - psi ** (n + 1)) / math.sqrt(5))
def climbStairs_combinatorial(n):
"""
Combinatorial approach
Sum of C(n-k, k) for k from 0 to floor(n/2)
Time: O(N)
Space: O(1)
"""
from math import comb
result = 0
for k in range(n // 2 + 1):
result += comb(n - k, k)
return result
# Example usage
print(climbStairs_formula(10)) # Output: 89
Java:
class Solution {
/**
* Mathematical approach using Binet's formula
* Time: O(1)
* Space: O(1)
*/
public int climbStairs(int n) {
double phi = (1 + Math.sqrt(5)) / 2;
double psi = (1 - Math.sqrt(5)) / 2;
return (int) Math.round((Math.pow(phi, n + 1) - Math.pow(psi, n + 1)) / Math.sqrt(5));
}
/**
* Combinatorial approach
* Time: O(N)
* Space: O(1)
*/
public int climbStairsCombinatorial(int n) {
long result = 0;
for (int k = 0; k <= n / 2; k++) {
result += combination(n - k, k);
}
return (int) result;
}
private long combination(int n, int k) {
if (k > n - k) k = n - k; // Take advantage of symmetry
long result = 1;
for (int i = 0; i < k; i++) {
result = result * (n - i) / (i + 1);
}
return result;
}
}
Key Insights
- Fibonacci Pattern: The problem is equivalent to computing the (n+1)th Fibonacci number
- Optimal Substructure: To reach step n, you must come from either step (n-1) or step (n-2)
- Overlapping Subproblems: Naive recursion recalculates the same states multiple times
- State Transition: ways(n) = ways(n-1) + ways(n-2)
- Space Optimization: Only need to track the last two computed values
Edge Cases
- n = 1: Only one way (single step)
- n = 2: Two ways (1+1 or 2)
- Large n: Consider integer overflow for very large inputs
- Base case handling: Ensure correct initialization for small values
Test Cases
def test_climbing_stairs():
test_cases = [
(1, 1),
(2, 2),
(3, 3),
(4, 5),
(5, 8),
(6, 13),
(10, 89)
]
for n, expected in test_cases:
assert climbStairs_optimized(n) == expected
print(f"stairs({n}) = {expected} ✓")
test_climbing_stairs()
Common Mistakes
- Wrong base cases: Using incorrect initial values
- Off-by-one errors: Incorrect loop bounds or indexing
- Integer overflow: Not handling large results properly
- Inefficient recursion: Using naive recursion without optimization
- Misunderstanding the problem: Confusing with other stair-climbing variations
Follow-up Questions
- Variable step sizes: What if you can climb 1, 2, or 3 steps at a time?
- Cost climbing: What if each step has a cost and you want to minimize total cost?
- Restricted steps: What if certain steps are broken and cannot be used?
- Multi-dimensional: What about climbing stairs in a 2D grid?
- Minimum steps: What’s the minimum number of steps to reach the top?
- Path reconstruction: How would you return the actual sequences of steps?
Interview Tips
- Recognize the pattern: Identify this as a Fibonacci-like sequence
- Start simple: Begin with recursive solution, then optimize
- Discuss tradeoffs: Compare different approaches and their complexities
- Handle edge cases: Make sure to test small values of n
- Optimize incrementally: Show progression from memoization to space optimization
- Explain the math: If time permits, discuss the mathematical relationship