Climbing Stairs: 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?

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

Try this Problem on your own or check similar problems:

1. Fibonacci Number
2. Unique Paths
3. Decode Ways

Solution:

public int climbStairs(int n) {
    if (n <= 1) {
        return 1;
    }
    int twoStepsBehind = 1, stepBehind = 2;
    for(int i = 3; i <= n; ++i){
        int currentTotal = twoStepsBehind + stepBehind;
        twoStepsBehind = stepBehind;
        stepBehind = currentTotal;
    }
    return stepBehind;
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Explanation:

Of course, this is the optimized solution, so let’s break down the thinking process leading to this solution. Your first hint should be that there is explicit recurrence in the problem statement: we have to reach a known goal (n stairs), and to get there we can only take 1 or 2 steps. So, let’s say we’re almost at the n step (mission completed) what previous stairs are we interested in? Well since we can only use 1 or 2 steps, we are only interested in stairs n-1 and n-2. So the recurrence relation would be waysToClimb(n) = waysToClimb(n-1) + waysToClimb(n-2). How can we guarantee that the ways will be distinct? Well, the difference is in the last step (in other words you will either use 1 or 2 steps to reach the final goal from the sub goal). Now that we have this formula it’s easy to spot that this falls under the category of DP (dynamic programming) problems. So how do we solve those? Here is a “framework” I’ve used to get my mind around DP problems (it consists of 6 steps):

1. Category
2. States
3. Decisions
4. Base Case
5. Code
6. Optimize (Time or Space Complexity)

So, let’s break down each of these steps:

Most of the DP problems fall into one of the following categories:

1. 0/1 Knapsack
2. Unbounded Knapsack
3. Shortest/Critical Path
4. Fibonacci Sequence
5. Longest Common Substring/Subsequence

All these categories will be mentioned later once they fit to the problem statement. For now, let’s focus on this problem, since the final state is dependent on the step before and two steps before it perfectly matches Fibonacci Sequence.

Next on how do we find states? States are generally information we need to keep as we move to the optimal/base case. It can be a helper sum array, indices, index difference, so basically the minimal number (because we have to reduce the space complexity) of information we need to carry with us as we move to the optimal/base solution.

What decisions we need to make to arrive at the optimal/base case? In this problem it’s easy since it’s given by problem statement, you can either take 1 or 2 steps, so your decision from the current state is either to take 1 or 2 steps.

Base case comes from the recursion stop point logic, in essence when do we stop calculating our formula. It can be that we have reached (or started) from base states (states given as part of the problem, in our case we know that we can reach stair 1 in only one way that is take 1 step, and step 2 in 2 ways 1+1 or 2). When we reach n stairs we know that we are at our desired step/goal.

Using this logic, we can code up a solution using recursion:

public int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    return climbStairs(n-1) + climbStairs(n-2);
}

But the complexity of this solution is O(n) for space complexity (because of the recursion stack) and time complexity O(2^n) (at each step for n steps we have 2 calls). How do we reduce complexity, well we know that our pain point is time complexity so we can shift a bit of responsibility/cost to space. We can use memoization (note different than memorization), so what does it mean? It means that we can store expensive recursion calls in auxiliary data structure (often variables like this are called memo) like hashmap, hashset and similar. This helps us to only calculate value for the subproblem (previous stair) once and every other time retrieve the value from the memo (you can think of it as cache for expensive operations):

class Solution {
    public int climbStairs(int n) {
        Map<Integer, Integer> memo = new HashMap<>() {{
            put(1, 1);
            put(2, 2);
        }};
        return climbStairs(n, memo);
    }
    private int climbStairs(int n, Map<Integer, Integer> memo) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        memo.put(n, climbStairs(n - 1, memo) + climbStairs(n - 2, memo));
        return memo.get(n);
    }
}

This is a top down approach (starting with desired goal and breaking down to subproblems) and will result in O(n) for both space and time complexity (at most n elements stored in hashmap). Can we optimize further?

Well let’s first introduce the bottom up approach:

public int climbStairs(int n) {
    if (n <= 1) {
        return 1;
    }

    int[] dp = new int[n + 1];
    dp[1] = 1; dp[2] = 2;

    for(int i = 3; i <= n; ++i){
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

We get the same space complexity, but we first calculate the “leaf” (if you imagine the recursion as a tree) subproblems and then move upwards. One thing we can note is that for each stair we only need to hold the value at 2 steps behind and value at the value 1 step behind, so do we need the whole array? No, we can reduce the space complexity to constant by tracking only two stairs, for each stair we are trying to apply the formula for (as shown in the initial solution).

So, there we have it, we moved from encrypting what the problem really is, to recursive approach using the recurrence relation formula we found by analyzing the problem statement, we moved to top down and bottom-up approach to reduce complexity by using memorization and then finally optimized further by removing the need for helper data structure thus reducing the space complexity.