Climbing Stairs Solution for Accenture
Company: Accenture · Difficulty: Easy · Topics: Dynamic Programming, Math
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?
Key Understanding:
- You can only climb 1 or 2 steps at a time
- You need to find the total number of distinct ways to reach the top
- The order of steps matters (1+2 is different from 2+1)
- This is a classic Fibonacci sequence problem
- The solution involves finding patterns in the number of ways
Examples
Example 1:
Input: n = 2
Output: 2
Explanation:
- There are two ways to climb to the top:
1. 1 step + 1 step = [1,1]
2. 2 steps = [2]
- Visual representation:
```
Step 0 → Step 1 → Step 2
| | |
| [1,1] [2]
| | |
| [1,2] [2]
```
Example 2:
Input: n = 3
Output: 3
Explanation:
- There are three ways to climb to the top:
1. 1 step + 1 step + 1 step = [1,1,1]
2. 1 step + 2 steps = [1,2]
3. 2 steps + 1 step = [2,1]
- Visual representation:
```
Step 0 → Step 1 → Step 2 → Step 3
| | | |
| [1,1] [1,1,1] [1,2]
| | | |
| [2] [2,1] [2]
```
Example 3:
Input: n = 4
Output: 5
Explanation:
- There are five ways to climb to the top:
1. 1+1+1+1 = [1,1,1,1]
2. 1+1+2 = [1,1,2]
3. 1+2+1 = [1,2,1]
4. 2+1+1 = [2,1,1]
5. 2+2 = [2,2]
Example 4:
Input: n = 5
Output: 8
Explanation:
- There are eight ways to climb to the top:
1. [1,1,1,1,1]
2. [1,1,1,2]
3. [1,1,2,1]
4. [1,2,1,1]
5. [1,2,2]
6. [2,1,1,1]
7. [2,1,2]
8. [2,2,1]
Intuition
The key insight is that this is a Fibonacci sequence problem. The number of ways to climb n steps is equal to the sum of ways to climb (n-1) steps and (n-2) steps.
Core Concept:
- To reach step n, you can come from step (n-1) by taking 1 step
- Or you can come from step (n-2) by taking 2 steps
- Therefore, ways(n) = ways(n-1) + ways(n-2)
Why This Works:
- This is the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, ...
- Each number is the sum of the two preceding ones
- The pattern emerges because of the constraint of only taking 1 or 2 steps
Mathematical Insight:
- Base cases: ways(1) = 1, ways(2) = 2
- Recurrence relation: ways(n) = ways(n-1) + ways(n-2)
- This is exactly the Fibonacci sequence starting from F(1) = 1, F(2) = 2
Pattern Recognition:
- n=1: 1 way
- n=2: 2 ways
- n=3: 3 ways (1+2)
- n=4: 5 ways (2+3)
- n=5: 8 ways (3+5)
- This clearly shows the Fibonacci pattern
Approach
Approach 1: Dynamic Programming (Optimal)
Algorithm:
1. Initialize two variables: prev = 1, curr = 2
2. For i from 3 to n:
- Calculate next = prev + curr
- Update prev = curr
- Update curr = next
3. Return curr
Why This Works:
- We use bottom-up dynamic programming
- We only need the last two values to calculate the next one
- This avoids recursion and uses constant space
- We build the solution iteratively
Complexity Analysis:
- Time: O(n) - We compute each value once
- Space: O(1) - We use only constant extra space
Approach 2: Recursion with Memoization
Algorithm:
1. Create a memoization array to store computed values
2. Define recursive function ways(n):
- If n <= 2, return n
- If memo[n] exists, return memo[n]
- Calculate memo[n] = ways(n-1) + ways(n-2)
- Return memo[n]
Why This Works:
- We use top-down dynamic programming
- We store computed values to avoid recalculation
- This prevents exponential time complexity
- We solve subproblems as needed
Complexity Analysis:
- Time: O(n) - Each value computed once
- Space: O(n) - Due to recursion stack and memoization
Approach 3: Matrix Exponentiation
Algorithm:
1. Use matrix exponentiation to find Fibonacci numbers
2. The Fibonacci sequence can be represented as matrix multiplication
3. Use fast exponentiation for O(log n) solution
Why This Works:
- Fibonacci numbers can be computed using matrix multiplication
- This is mathematically elegant and efficient for large n
- Useful when n is very large (e.g., n > 10^9)
Complexity Analysis:
- Time: O(log n) - Matrix exponentiation
- Space: O(1) - Constant space for matrix operations
Dry Run
Let's trace through Example 1: n = 2
Dynamic Programming Approach:
Step 1: Initialize
- prev = 1 (ways to climb 1 step)
- curr = 2 (ways to climb 2 steps)
Step 2: For n = 2
- Since n = 2, we return curr = 2
Result: 2 ways to climb 2 steps
Let's trace through Example 2: n = 3
Step 1: Initialize
- prev = 1, curr = 2
Step 2: For i = 3
- next = prev + curr = 1 + 2 = 3
- prev = curr = 2
- curr = next = 3
Step 3: Return curr = 3
Result: 3 ways to climb 3 steps
Let's trace through Example 3: n = 4
Step 1: Initialize
- prev = 1, curr = 2
Step 2: For i = 3
- next = 1 + 2 = 3
- prev = 2, curr = 3
Step 3: For i = 4
- next = 2 + 3 = 5
- prev = 3, curr = 5
Step 4: Return curr = 5
Result: 5 ways to climb 4 steps
Recursion with Memoization Approach:
Step 1: Create memo array
- memo = [0, 1, 2, 0, 0, ...]
Step 2: Calculate ways(4)
- ways(4) = ways(3) + ways(2)
- ways(3) = ways(2) + ways(1) = 2 + 1 = 3
- ways(2) = 2 (from memo)
- ways(4) = 3 + 2 = 5
Result: 5 ways to climb 4 steps
Key Insights
1. Fibonacci Pattern: The solution follows the Fibonacci sequence
2. Optimal Substructure: The problem can be broken down into smaller subproblems
3. Overlapping Subproblems: The same subproblems are solved multiple times
4. Constant Space: We only need the last two values to calculate the next one
5. Mathematical Elegance: The solution is mathematically beautiful and efficient
Edge Cases
1. n = 1: Return 1 (only one way: take 1 step)
2. n = 2: Return 2 (two ways: [1,1] or [2])
3. n = 0: Not valid input (constraints specify n ≥ 1)
4. Large n: Algorithm handles large values efficiently
5. Overflow: For very large n, consider using long long or modular arithmetic
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Dynamic Programming (Optimal)
Time Complexity: O(n) - We compute each value once
Space Complexity: O(1) - We use only constant extra space
Advantages:
- Most efficient solution
- Constant space usage
- Simple and intuitive
- No recursion overhead
Disadvantages:
- None for this problem
Solution 2: Recursion with Memoization
Time Complexity: O(n) - Each value computed once
Space Complexity: O(n) - Due to recursion stack and memoization
Advantages:
- Top-down approach
- Easy to understand
- Natural recursive structure
Disadvantages:
- Uses more space
- Recursion overhead
- Stack space usage
Solution 3: Matrix Exponentiation
Time Complexity: O(log n) - Matrix exponentiation
Space Complexity: O(1) - Constant space for matrix operations
Advantages:
- Most efficient for very large n
- Mathematical elegance
- Logarithmic time complexity
Disadvantages:
- More complex implementation
- Overkill for small values of n
- Requires understanding of matrix operations