Climbing Stairs

EasyDynamic ProgrammingMathMemoization
Category: 1-D Dynamic Programming
Companies that ask this question:
AmazonGoogleMicrosoftAdobeApple

Approach

Climbing Stairs

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?

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

Constraints

  • 1 ≤ n ≤ 45

Approach

Key Insight

This is a Fibonacci problem in disguise!

To reach step n, you can come from:

  • Step n-1 (take 1 step)
  • Step n-2 (take 2 steps)

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

Solution 1: Dynamic Programming (Bottom-Up)

Build the solution from the ground up.

Algorithm:

  1. Base cases: ways(1) = 1, ways(2) = 2
  2. For each step from 3 to n:
    • ways(i) = ways(i-1) + ways(i-2)
  3. Return ways(n)

Solution 2: Space-Optimized DP

We only need the last two values!

Algorithm:

  1. Keep only two variables: prev2 and prev1
  2. For each step:
    • current = prev1 + prev2
    • Shift: prev2 = prev1, prev1 = current
  3. Return prev1

Solution 3: Recursion with Memoization (Top-Down)

Recursively solve with caching.

Algorithm:

  1. Base cases: if n ≤ 2, return n
  2. Use memoization to avoid recalculating
  3. Return climb(n-1) + climb(n-2)

Complexity Analysis

DP Solution:

  • Time Complexity: O(n) - single pass
  • Space Complexity: O(n) - DP array (or O(1) if optimized)

Recursive with Memo:

  • Time Complexity: O(n) - each subproblem solved once
  • Space Complexity: O(n) - memoization cache + recursion stack

Pure Recursion (Not recommended):

  • Time Complexity: O(2^n) - exponential without memoization
  • Space Complexity: O(n) - recursion stack

Pattern Recognition

This problem demonstrates:

  • Dynamic Programming basics
  • Fibonacci sequence pattern
  • Bottom-up vs Top-down DP
  • Space optimization techniques
  • Foundation for many DP problems

Solution

java
1import java.util.*;
2
3class Solution {
4    // Solution 1: Dynamic Programming (Bottom-Up)
5    public int climbStairs(int n) {
6        // Handle base cases
7        if (n <= 2) return n;
8
9        // Create DP array
10        int[] dp = new int[n + 1];
11        dp[1] = 1;  // 1 way to reach step 1
12        dp[2] = 2;  // 2 ways to reach step 2
13
14        // Fill DP table
15        for (int i = 3; i <= n; i++) {
16            dp[i] = dp[i - 1] + dp[i - 2];
17        }
18
19        return dp[n];
20    }
21
22    // Solution 2: Space-Optimized DP (O(1) space)
23    public int climbStairsOptimized(int n) {
24        if (n <= 2) return n;
25
26        // Only keep track of last two values
27        int prev2 = 1;  // ways(1)
28        int prev1 = 2;  // ways(2)
29
30        for (int i = 3; i <= n; i++) {
31            int current = prev1 + prev2;
32            prev2 = prev1;
33            prev1 = current;
34        }
35
36        return prev1;
37    }
38
39    // Solution 3: Recursion with Memoization (Top-Down)
40    private Map<Integer, Integer> memo = new HashMap<>();
41
42    public int climbStairsMemo(int n) {
43        // Base cases
44        if (n <= 2) return n;
45
46        // Check memo
47        if (memo.containsKey(n)) {
48            return memo.get(n);
49        }
50
51        // Recursive case
52        int result = climbStairsMemo(n - 1) + climbStairsMemo(n - 2);
53        memo.put(n, result);
54
55        return result;
56    }
57}
58
Loading visualizer...