1. 📌 Problem Links

LeetCode 70: Climbing Stairs

2. 🧠 Solution Overview

This problem requires calculating how many distinct ways you can climb to the top of a staircase with n steps, taking either 1 or 2 steps at a time. Below are the main approaches:

Method	Key Idea	Time Complexity	Space Complexity
Dynamic Programming	Build solution using previous results	O(n)	O(n) or O(1)
Matrix Exponentiation	Mathematical approach using matrix power	O(log n)	O(1)
Brute Force Recursion	Basic recursive solution	O(2^n)	O(n)

3. 🟢 Solution 1: Dynamic Programming

3.1. Algorithm Idea

We use dynamic programming where dp[i] represents the number of ways to reach the i-th step. Since we can only take 1 or 2 steps at a time, the number of ways to reach step i equals the sum of ways to reach step i-1 (then take 1 step) and step i-2 (then take 2 steps). This creates a Fibonacci-like sequence.

3.2. Key Points

• State Definition: dp[i] = number of ways to reach step i
• State Transition: dp[i] = dp[i-1] + dp[i-2]
• Initialization:
  • dp[0] = 1 (ground level, 1 way to stay)
  • dp[1] = 1 (only one way: take 1 step)
  • Alternatively: dp[1] = 1, dp[2] = 2
• Processing Order: Fill from bottom up (2 to n)

3.3. Java Implementation

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        
        int[] dp = new int[n + 1];
        dp[0] = 1; // Ground level
        dp[1] = 1; // First step
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
}

3.4. Complexity Analysis

• Time Complexity: O(n) - Single loop through n steps
• Space Complexity: O(n) - DP array of size n+1

4. 🟡 Solution 2: Space-Optimized DP

4.1. Algorithm Idea

We can optimize space by using only two variables instead of an entire array. Since each step only depends on the previous two steps, we can maintain a rolling window of these two values and update them iteratively.

4.2. Key Points

• Variables: Use prev1 and prev2 to track previous two states
• State Maintenance:
  • current = prev1 + prev2
  • Update prev2 = prev1, prev1 = current
• Edge Cases: Handle n = 1 and n = 2 separately

4.3. Java Implementation

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        
        int prev1 = 2; // Ways for n=2
        int prev2 = 1; // Ways for n=1
        
        for (int i = 3; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
}

4.3. Java Implementation (Alternative)

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

4.4. Complexity Analysis

• Time Complexity: O(n) - Same as standard DP
• Space Complexity: O(1) - Only constant extra space used

5. 🔵 Solution 3: Matrix Exponentiation

5.1. Algorithm Idea

This mathematical approach uses matrix exponentiation to achieve logarithmic time complexity. The recurrence relation can be represented as matrix multiplication, and we can use exponentiation by squaring to compute the result efficiently.

5.2. Key Points

• Matrix Form: Represent as [F(n), F(n-1)] = [F(n-1), F(n-2)] * M
• Transformation Matrix: M = [[1, 1], [1, 0]]
• Exponentiation: Compute M^n using binary exponentiation in O(log n) time

5.3. Java Implementation

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        
        int[][] base = {{1, 1}, {1, 0}};
        int[][] result = matrixPower(base, n);
        
        return result[0][0];
    }
    
    private int[][] matrixPower(int[][] matrix, int power) {
        int[][] result = {{1, 0}, {0, 1}}; // Identity matrix
        
        while (power > 0) {
            if ((power & 1) == 1) {
                result = multiplyMatrices(result, matrix);
            }
            matrix = multiplyMatrices(matrix, matrix);
            power >>= 1;
        }
        
        return result;
    }
    
    private int[][] multiplyMatrices(int[][] a, int[][] b) {
        int[][] result = new int[2][2];
        result[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
        result[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
        result[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
        result[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
        return result;
    }
}

5.4. Complexity Analysis

• Time Complexity: O(log n) - Due to exponentiation by squaring
• Space Complexity: O(1) - Constant space for matrices

6. 📊 Solution Comparison

Solution	Time	Space	Pros	Cons
Standard DP	O(n)	O(n)	Intuitive, easy to understand	Higher memory usage
Optimized DP	O(n)	O(1)	Best for interviews, balanced	Still linear time
Matrix Exponentiation	O(log n)	O(1)	Optimal time complexity	Complex implementation

7. 💡 Summary

For the Climbing Stairs problem:

• Standard DP is most intuitive and recommended for understanding the core concept
• Space-optimized DP offers the best practical solution for interviews and general use
• Matrix Exponentiation provides theoretical optimal time but is overkill for most scenarios

The key insight is recognizing this as a Fibonacci sequence problem where each step builds upon previous solutions.

The journey of a thousand steps begins with a single step, and each subsequent step is built upon the wisdom of the ones before - much like dynamic programming teaches us about solving complex problems through simpler subproblems.