Climbing Stairs is probably the first problem that forces you to actually think about optimization. For many people, it’s also their first real introduction to Dynamic Programming (DP). At its core, DP is just the idea of remembering work you’ve already done so you don’t repeat it. It’s a great problem to get your feet wet in that domain.
The Problem
The problem asks that you climb a staircase by either taking one step or two steps. How many distinct ways can we climb to the top given a stair case of size n?
For example, if we are given a staircase of size 2 then there are only two ways to climb to the top.
- 1 step + 1 step
- 2 steps
Similarly if n was 3 then we would have 3 ways to climb the staircase:
- 1 step + 1 step + 1 step
- 2 steps + 1 step
- 1 step + 2 steps
Solution
Lets try to solve this problem by brute force by hand first. If we try to write out solutions by hand we will start to notice an interesting pattern:
If n was 4 we would have 5 ways to climb the stairs
- 1 step + 1 step + 1 step + 1 step
- 2 steps + 1 step + 1 step
- 1 step + 2 steps + 1 step
- 1 step + 1 step + 2 steps
- 2 steps + 2 steps
Similarly if we do n = 5 we would get 8 (I’ll skip writing out all the possible combinations). More importantly we would notice an interesting pattern emerge:
If n = 1 then we get 1
If n = 2 then we get 2
If n = 3 then we get 3
If n = 4 then we get 5
If n = 5 then we get 8
…. and so on
Do you see the pattern? Each number is the sum of the two before it. That’s just the Fibonacci sequence. This whole problem reduces to computing Fibonacci numbers.
Naive Solution
Anyways, the naive solution is to code the sequence using recursion:
public static int climbStairs(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
We set up a base case for the first two numbers in the sequence and otherwise we would work our way backwards to find the solution we need. This would give us the correct solution but this would not be accepted by LeetCode. It would get rejected not because it’s incorrect but because it’s too slow. As N gets large the function becomes slower dramatically.
Naive Solution Time and Space Complexity
How slow exactly? Let’s find out. If we graph out an execution of this method for n = 5 the recursions make a pretty binary tree for us:
climbStairs(5)
├── climbStairs(4)
│ ├── climbStairs(3)
│ │ ├── climbStairs(2) → 2
│ │ └── climbStairs(1) → 1
│ └── climbStairs(2) → 2
└── climbStairs(3)
├── climbStairs(2) → 2
└── climbStairs(1) → 1
If we count each node in this tree as an execution of our method then this means the cost to run this solution will grow exponentially as n gets bigger. In general that means that our algorithm has a time complexity of O(2^N). Since the computer walks through this tree depth first (it goes from the root to one leaf before it visits another leaf) the space complexity is O(N) since the path from the root to the leaf of the tree would be at most N. As a result at most N calls of the recursive function would be on the call stack (and thus memory) at any given time.
Memoized Solution
We can make this program much faster by taking advantage of a pattern we see in the tree above. We often repeat the same work throughout the tree. What if instead of redoing that we remembered what we had done last time and used that? The act of remembering previous calculations is the core technique of dynamic programming. We can store the results of previous calculations in a variable called memo and do the same calculations as we go.
public static int climbStairs(int n) {
List<Integer> memo = new ArrayList<>();
// take care of our base cases of when n = 0, 1, or 2
memo.add(0);
memo.add(1);
memo.add(2);
while(n >= memo.size()) {
int currentSize = memo.size();
memo.add(memo.get(currentSize - 1) + memo.get(currentSize - 2));
}
return memo.get(n);
}Like before we record some values for the base cases but instead of calling the function over and over we just look at the last two values we calculated to determine the next one. Since we only ever do calculation for a new number once this solution is much faster.
Memoized Time and Space Complexity
How much faster? Well if we are only ever calculating new numbers once then at most the number of times we would calculate numbers in the sequence is O(n). Similarly, since our code needs to store an array of size n our space complexity remains O(n).
Optimal Space Solution
We can do even better than this in terms of space though. Since we only really need to remember the last two values it doesn’t make sense to keep all the old values we calculated in an array. Instead we could just keep track of the last two values to be more efficient.
public int climbStairs(int n) {
int current = 2;
int before = 1;
if (n == 1) {
return before;
}
if (n == 2) {
return current;
}
int temp;
for(int i = 3; i <= n; i++) {
temp = before;
before = current;
current = temp + before;
}
return current;
}
This lets us keep our O(n) speed but actually reduces our space usage to just O(1).
Key Takeaways
The solution starts off as a straightforward variation of generating the fibonacci sequence but forces the user to approach the same problem with a different mindset as they run against performance constraints. In many ways this program is a great introduction to dynamic programming and evolving past beginner programming challenges to more advanced problems.
