1D Dynamic Programming (Climbing Stairs)

The Climbing Stairs problem is a classic dynamic programming example that demonstrates how many real-world problems reduce to Fibonacci-style recurrence relations.

It is one of the simplest ways to practice identifying DP state, transitions, and base cases.

Problem Statement

You are climbing a staircase with n steps.

• You can climb 1 step or 2 steps at a time
• In how many distinct ways can you reach the top?

Example

For n = 4, the valid ways are:

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

So the answer is 5.

Key Insight

To reach step n:

• You must come from step n - 1 (1 step)
• Or from step n - 2 (2 steps)

Therefore:

ways(n) = ways(n - 1) + ways(n - 2)

This is exactly the Fibonacci recurrence.

DP State Definition

Let:

dp[i] = number of ways to reach step i

Base Cases

dp[0] = 1  // one way to stay at the ground
dp[1] = 1  // one way to take one step

Bottom-Up DP (Tabulation)

Rust Implementation

pub fn climb_stairs(n: usize) -> usize {
    if n <= 1 {
        return 1;
    }

    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]
}

Space Optimization (O(1) Space)

Only the previous two states are needed.

pub fn climb_stairs_optimized(n: usize) -> usize {
    if n <= 1 {
        return 1;
    }

    let mut prev2 = 1;
    let mut prev1 = 1;

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

    prev1
}

Top-Down DP (Memoization)

use std::collections::HashMap;

pub fn climb_stairs_memo(n: usize) -> usize {
    let mut memo = HashMap::new();
    helper(n, &mut memo)
}

fn helper(n: usize, memo: &mut HashMap<usize, usize>) -> usize {
    if n <= 1 {
        return 1;
    }

    if let Some(&val) = memo.get(&n) {
        return val;
    }

    let result = helper(n - 1, memo) + helper(n - 2, memo);
    memo.insert(n, result);
    result
}

Time and Space Complexity

Time Complexity

Space Complexity

Why This Problem Matters

Climbing Stairs teaches you how to:

• Identify DP state
• Write recurrence relations
• Choose base cases
• Optimize space
• Recognize Fibonacci-like problems

Many problems are exactly this, with different wording.

Common Variations

• Steps of 1, 2, or 3
• Cost associated with each step
• Minimum cost to climb stairs
• Ways modulo k

All build on the same DP pattern.

Summary

• Climbing Stairs is a 1D DP problem
• Uses Fibonacci-style recurrence
• Easy to optimize space
• Foundation for more complex DP problems