Climbing Stairs

Problem Statement

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?

What to notice first

• You start at step 0 and want to reach step n.
• At each step, you have exactly 2 choices: take 1 step or take 2 steps.
• The order of choices matters: [1, 1, 2] is different from [1, 2, 1].
• Each subproblem (reaching step i) depends on previous subproblems.

Examples

n	Output	Explanation
2	2	[1, 1] or [2]
3	3	[1, 1, 1], [1, 2], or [2, 1]
4	5	[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], or [2, 2]
5	8	Follow Fibonacci sequence

Constraints

• 1 <= n <= 45

Real-World Applications

Where this pattern appears

• Navigation menus — counting distinct paths through multi-level menus with step sizes.
• Robotics path planning — discrete movement options and counting total routes to a destination.
• Game AI — determining number of move sequences to reach a target position with limited step sizes.
• Password generation — breaking a string into chunks of size 1 or 2 (word break variants).

Complexity Comparison

Approach	Time	Space	Description
DP Array	O(n)	O(n)	Store all values, easy to understand and debug
Fibonacci Variables	O(n)	O(1)	Only keep last two values, space-optimized

Which approach should you learn first?

• Pick DP Array if you want the clearest explanation and debugging capability.
• Pick Fibonacci Variables if you want to optimize space and understand the Fibonacci connection.

Best For Understanding

DP Array

O(n) time · O(n) space

Space Optimized

Fibonacci Variables

O(n) time · O(1) space

Approach 1: DP Array

★ Recommended

Build a dynamic programming array where dp[i] represents the number of distinct ways to reach step i.

The recurrence relation is simple: to reach step i, you can either:

• Come from step i-1 and take 1 step
• Come from step i-2 and take 2 steps

Therefore: dp[i] = dp[i-1] + dp[i-2]

⏱ Time O(n) Single pass 💾 Space O(n) DP array storage

Step-by-step Example

Input: n = 4

Step i	dp[i]	Ways to reach step i
0	1	Base case (starting point)
1	1	[1]
2	2	[1, 1], [2]
3	3	[1, 1, 1], [1, 2], [2, 1]
4	5	[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]

Animated walkthrough

How the DP array solution counts paths

Use Next or Autoplay to watch the DP array build step by step, showing how each new value is the sum of the previous two.

Back Autoplay Next Reset

Step 1 of 4 Target: 4

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function climbingStairsDpArray(n):
    if n <= 1:
        return 1
    dp = array of size n+1
    dp[0] = 1
    dp[1] = 1
    for i from 2 to n:
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Solution Code

Python

climbing_stairs_dp_array.py

from typing import List


def climbing_stairs_dp_array(n: int) -> int:
    """
    Climb n stairs with dp array approach.

    Time Complexity: O(n)
    Space Complexity: O(n)

    At each step i, we can either:
    - Come from step i-1 and take 1 step
    - Come from step i-2 and take 2 steps
    So dp[i] = dp[i-1] + dp[i-2]
    """
    if n <= 1:
        return 1

    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]


if __name__ == "__main__":
    print(climbing_stairs_dp_array(3))   # 3 (1+1+1, 1+2, 2+1)
    print(climbing_stairs_dp_array(4))   # 5
    print(climbing_stairs_dp_array(5))   # 8

C++

climbing_stairs_dp_array.cpp

#include <iostream>
#include <vector>

using namespace std;

/**
 * Climb n stairs with dp array approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
int climbingStairsDpArray(int n) {
    if (n <= 1) return 1;

    vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    cout << climbingStairsDpArray(3) << endl;  // 3
    cout << climbingStairsDpArray(4) << endl;  // 5
    cout << climbingStairsDpArray(5) << endl;  // 8
    return 0;
}

Java

ClimbingStairsDpArray.java

/**
 * Climb n stairs with dp array approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
public class ClimbingStairsDpArray {
    public static int climbingStairsDpArray(int n) {
        if (n <= 1) return 1;

        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(climbingStairsDpArray(3));  // 3
        System.out.println(climbingStairsDpArray(4));  // 5
        System.out.println(climbingStairsDpArray(5));  // 8
    }
}

JavaScript

climbing_stairs_dp_array.js

/**
 * Climb n stairs with dp array approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
function climbingStairsDpArray(n) {
    if (n <= 1) return 1;

    const dp = new Array(n + 1);
    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

console.log(climbingStairsDpArray(3));  // 3
console.log(climbingStairsDpArray(4));  // 5
console.log(climbingStairsDpArray(5));  // 8

Rust

climbing_stairs_dp_array.rs

/**
 * Climb n stairs with dp array approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
pub fn climbing_stairs_dp_array(n: i32) -> i32 {
    if n <= 1 {
        return 1;
    }

    let n = n as usize;
    let mut dp = vec![0; n + 1];
    dp[0] = 1;
    dp[1] = 1;

    for i in 2..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    dp[n]
}

fn main() {
    println!("{}", climbing_stairs_dp_array(3));  // 3
    println!("{}", climbing_stairs_dp_array(4));  // 5
    println!("{}", climbing_stairs_dp_array(5));  // 8
}

Go

climbing_stairs_dp_array.go

package main

import "fmt"

/*
 * Climb n stairs with dp array approach.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
func climbingStairsDpArray(n int) int {
  if n <= 1 {
    return 1
  }

  dp := make([]int, n+1)
  dp[0] = 1
  dp[1] = 1

  for i := 2; i <= n; i++ {
    dp[i] = dp[i-1] + dp[i-2]
  }

  return dp[n]
}

func main() {
  fmt.Println(climbingStairsDpArray(3))  // 3
  fmt.Println(climbingStairsDpArray(4))  // 5
  fmt.Println(climbingStairsDpArray(5))  // 8
}

Approach 2: Fibonacci Variables (Space-Optimized)

🎯 Interview Favourite

Instead of storing all n values, we only keep track of the last two values (prev1 and prev2) since dp[i] only depends on dp[i-1] and dp[i-2].

This approach recognizes that the climbing stairs problem follows the Fibonacci sequence.

⏱ Time O(n) Single pass 💾 Space O(1) Only two variables

Step-by-step Example

Input: n = 4

Iteration	prev2	prev1	current = prev1 + prev2	Interpretation
Start	1	1	—	Base cases
i=2	1	2	2	2 ways to reach step 2
i=3	2	3	3	3 ways to reach step 3
i=4	3	5	5	5 ways to reach step 4

Why this works

The Fibonacci sequence naturally appears because each number is the sum of the two preceding ones. The number of ways to reach step n is the (n+1)-th Fibonacci number.

Pseudocode

function climbingStairsFibonacciVariables(n):
    if n <= 1:
        return 1
    prev2 = 1
    prev1 = 1
    for i from 2 to n:
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    return prev1

Solution Code

Python

climbing_stairs_fibonacci_variables.py

def climbing_stairs_fibonacci_variables(n: int) -> int:
    """
    Climb n stairs with Fibonacci variables approach (space-optimized).

    Time Complexity: O(n)
    Space Complexity: O(1)

    Instead of storing all values in an array, we only keep the last two
    values since dp[i] only depends on dp[i-1] and dp[i-2].
    """
    if n <= 1:
        return 1

    prev2 = 1  # dp[0]
    prev1 = 1  # dp[1]

    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1


if __name__ == "__main__":
    print(climbing_stairs_fibonacci_variables(3))   # 3 (1+1+1, 1+2, 2+1)
    print(climbing_stairs_fibonacci_variables(4))   # 5
    print(climbing_stairs_fibonacci_variables(5))   # 8

C++

climbing_stairs_fibonacci_variables.cpp

#include <iostream>

using namespace std;

/**
 * Climb n stairs with Fibonacci variables approach (space-optimized).
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
int climbingStairsFibonacciVariables(int n) {
    if (n <= 1) return 1;

    int prev2 = 1;  // dp[0]
    int prev1 = 1;  // dp[1]

    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

int main() {
    cout << climbingStairsFibonacciVariables(3) << endl;  // 3
    cout << climbingStairsFibonacciVariables(4) << endl;  // 5
    cout << climbingStairsFibonacciVariables(5) << endl;  // 8
    return 0;
}

Java

ClimbingStairsFibonacciVariables.java

/**
 * Climb n stairs with Fibonacci variables approach (space-optimized).
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
public class ClimbingStairsFibonacciVariables {
    public static int climbingStairsFibonacciVariables(int n) {
        if (n <= 1) return 1;

        int prev2 = 1;  // dp[0]
        int prev1 = 1;  // dp[1]

        for (int i = 2; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }

    public static void main(String[] args) {
        System.out.println(climbingStairsFibonacciVariables(3));  // 3
        System.out.println(climbingStairsFibonacciVariables(4));  // 5
        System.out.println(climbingStairsFibonacciVariables(5));  // 8
    }
}

JavaScript

climbing_stairs_fibonacci_variables.js

/**
 * Climb n stairs with Fibonacci variables approach (space-optimized).
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
function climbingStairsFibonacciVariables(n) {
    if (n <= 1) return 1;

    let prev2 = 1;  // dp[0]
    let prev1 = 1;  // dp[1]

    for (let i = 2; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

console.log(climbingStairsFibonacciVariables(3));  // 3
console.log(climbingStairsFibonacciVariables(4));  // 5
console.log(climbingStairsFibonacciVariables(5));  // 8

Rust

climbing_stairs_fibonacci_variables.rs

/**
 * Climb n stairs with Fibonacci variables approach (space-optimized).
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
pub fn climbing_stairs_fibonacci_variables(n: i32) -> i32 {
    if n <= 1 {
        return 1;
    }

    let mut prev2 = 1;  // dp[0]
    let mut prev1 = 1;  // dp[1]

    for _ in 2..=n {
        let current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    prev1
}

fn main() {
    println!("{}", climbing_stairs_fibonacci_variables(3));  // 3
    println!("{}", climbing_stairs_fibonacci_variables(4));  // 5
    println!("{}", climbing_stairs_fibonacci_variables(5));  // 8
}

Go

climbing_stairs_fibonacci_variables.go

package main

import "fmt"

/*
 * Climb n stairs with Fibonacci variables approach (space-optimized).
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
func climbingStairsFibonacciVariables(n int) int {
  if n <= 1 {
    return 1
  }

  prev2 := 1  // dp[0]
  prev1 := 1  // dp[1]

  for i := 2; i <= n; i++ {
    current := prev1 + prev2
    prev2 = prev1
    prev1 = current
  }

  return prev1
}

func main() {
  fmt.Println(climbingStairsFibonacciVariables(3))  // 3
  fmt.Println(climbingStairsFibonacciVariables(4))  // 5
  fmt.Println(climbingStairsFibonacciVariables(5))  // 8
}

Common mistakes

Watch for these pitfalls

• Forgetting base cases: dp[0] and dp[1] must be initialized correctly.
• Off-by-one errors in loop bounds: the loop should go from 2 to n (inclusive).
• Confusing the recurrence: it’s dp[i] = dp[i-1] + dp[i-2], not multiplication or other operations.
• In the Fibonacci approach, not updating prev2 before prev1, which breaks the recurrence.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

climbing_stairs_space_optimized.py

def solution(): return 0

C++

climbing_stairs_space_optimized.cpp

int main() { return 0; }

Java

ClimbingStairsSpaceOptimized.java

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int prev = 1, curr = 2;
        for (int i = 3; i <= n; i++) {
            int next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

System.out.println(new Solution().climbStairs(4));

JavaScript

climbing_stairs_space_optimized.js

function solution() { return 0; }
module.exports = solution;

Rust

climbing_stairs_space_optimized.rs

pub fn solution() -> i32 { 0 }

Go

climbing_stairs_space_optimized.go

package main
func solution() int { return 0 }

Related Problems

• Delete and Earn ↗ Medium #740
• House Robber ↗ Medium #198
• House Robber II ↗ Medium #213
• Two Sum ↗ Easy #1

Interview Tips

Key trade-offs to discuss

• Why DP over brute force? Brute force would explore 2^n paths through recursion. DP reduces it to O(n) by storing intermediate results.
• Space optimization: The Fibonacci variables approach shows you understand the problem deeply enough to optimize unused state. Many interviewers appreciate this.
• Connection to Fibonacci: Mentioning the Fibonacci sequence shows mathematical insight and helps with memoization interview follow-ups.
• Edge cases: Handle n=1 and n=2 explicitly; they are base cases. For n=0, return 1 (already at destination).

← Previous
#69 Sqrt(x) Next
#71 Simplify Path →