Improving big o in climbing stairs (recursion) with memoization

In the climbing stairs problem (leetcode), we are asked to find in how many ways we can climb a set of stairs either taking one step or two steps. So to climb a set of 3 stairs we can take 3 one steps, or 1 step and then a 2 step, or a 2 step and then 1 step.

The way this problem is solved is by building a 'binary tree' where we add either 1 or 2 to the current step. Each recursion is a leaf on the tree.

               (step,target)
                   [0,3]
                /         \
             [1,3]        [2,3]
            /    \        /    
         [2,3]  [3,3]   [3,3]  
         /
      [3, 3] 

So we use two recursions every time well call the function and each one is a 'branch' of the tree. In one of the recursions we add 1 step and in the other one add 2 steps and whenever we find we reached the target step level or the 'top of the stairs' we return 1 and so the count of ways to reach the target increases. There are many recursions happening as the time complexity is very high at O(2^n).

const recursionTreeSlow = (topStair) => {
    return recursion_Tree_Slow(0, topStair)
}

const recursion_Tree_Slow = (currentStair, topStair) => {
    if(currentStair> topStair){
        return 0
    }
    if(currentStair=== topStair){
        return 1
    }
    let countWaysOfClimbing = recursion_Tree_Slow(currentStair+1, topStair) + recursion_Tree_Slow(currentStair+2, topStair)
    return countWaysOfClimbing
}

This solution works by 'brute force' traveling to every node once or calling a recursive function for every leaf in the tree, but if we can store the data somehow and reuse old recursions that are the same as the pattern repeats in the tree, we can improve the algorithm and with the help of a memo key-value pair data structure, can achieve this.

I should mention that I gave some intuitive names to the variables in this example, to try and make this more accessible to other people with a non-CS background like me (self-taught or bootcamp), but please let me know if this helps or not :)

First let's review the variables

Comparing to leetcode I did:

• iteration index: i (currentStair)
• the passed argument n (topStair) which is the depth of the tree and in this example how many steps we need to climb
• the memo object (treeData).

But i, n, and memo are the traditional variable names used in these types of problems.

Memoization

To improve the runtime of this problem we 'memoize' the data and eliminate unnecessary operations. So the key (currentStair ) will represent the current step to the target and the value (countOfWaysToClimb) is the count of different ways to reach the target from that stair.

 treeData[currentStair] = countOfWaysToClimb 

The object treeData serves to store and access the node values in a key-value pair structure and nodes that have the same values will be the same and won't be recreated.

Especifically on this example:

                  (step, target)
                      [0,4]
                  /            \
              [1,4]            [2,4]
            /       \           /    \
         [2,4]       [3,4]    [3,4]  [4,4]
         /    \        /       /
      [3, 4] [4,4]   [4,4]    [4,4] 
     /
   [4,4] 

The node [2,4] repeats twice so whenever we arrive at the right [2,4] node we already know the results of the subsequent recursions, knowing that there will be 2 ways to reach [4,4]. As you can see the leafs of [2,4] are identical.

Checkout the code with some console.logs

const recursionTreeMemoization = (topStair) => {
    const treeData = {}
    return recursion(0, topStair, treeData)
}

const recursion = (currentStair, topStair, treeData) => {
    if (currentStair> topStair){
        return 0
    }
    if (currentStair=== topStair){
        return 1
    }
    if (treeData[currentStair] > 0){
        return treeData[currentStair]
    }
    treeData[currentStair] = recursion(currentStair+ 1, topStair, treeData) + recursion(currentStair+ 2,topStair, treeData)

    return treeData[currentStair]
}

So the whenever treeData[currentStair] > 0 is true it means that we already have a count of ways from that current stair stored in our treeData data object. So we just recall that count and add it to the current count and to accumulate the count.

Please feel more than welcome to reach out!

Connect with me on LinkedIn
or Twitter!