Hey everyone. I’d like to share a pretty popular Dynamic Programming algorithm I came across recently solving LeetCode Explore problems.

It’s super cool.

The algorithm asks us, given n (which is the staircase number/step), how many ways can we reach it taking only one or two steps at a time?

### Here is the video breakdown. If you prefer reading, keep on scrolling 🙂

### Here is the full code below. Scroll, for the explanation:

If you have not noticed, this algorithm follows the fibonacci sequence. 1 and 2 are our base cases. To get to step 1 is one step and to reach at step 2 is two steps. To arrive at step 3 we add the last two steps before it.

First, we will define a function called *climbStairs()*, which takes *n* – the staircase number- as an argument. Next, we create an empty dictionary called *store, *which will be used to store calculations we have already made. For example, if n = 5, we know that to find the answer, we need to add staircase number 3 and 4. Instead of recalculating how to reach staircase 3 and 4 we can just check to see if they are in the dictionary, and just add their values.

Within the* climbStairs()* function, we will have another helper function. We are building a function within a function because we need to keep our dictionary outside of the recursion we’ll be doing in the helper function. With only one function, the *store* dictionary would reset every time. The helper() function also takes n as an argument. As stated above, 1 and 2 are our base cases. These two numbers are the building blocks of our algorithm. If n = 1 or n =2, we will just return it.

In alignment with the above if statement we have our elif statement. This statement will check to see if our current value of n is already in the dictionary, so that we do not have to recalculate it again. This is *memoization. *Storing values to avoid recalculation.

### Long Explanation BreakDown Below!

The else statement below is where the recursive magic happens. This is the first statement we will hit when n does not equal 1 or 2. If *n = 5*, we add the key, *5, *to our *store* dictionary and then begin the calculations. We hit *helper(n-1),* which will call our helper function again as *helper(4)*. Now that *n = 4*, we reach our else statement again and add 4 to our *store* dictionary. We hit *helper(n-1)* again, so we call the helper function again as *helper(3)*. Once again we reach our else statement as *n* does not equal 1 or 2 and n, which is *3* at the moment, is not yet stored in the dictionary. In the else statement, we now *store[3]*, as a key in the dictionary and call *helper(n-1)*, which is translation for *helper(3-1) *or *helper(2)*. *helper(2)* is called and finally we hit our first base case. *n* now equals *2* so we return *2*. Now, that 2 has been returned, *n* snakes back and becomes *3*. For 3, we are finished with *helper(n-1)*, as the result of that is now 2. Now, for 3 we move on to the next helper function, *helper(n-2)*. Which is really *helper(3-2)* or *helper(1)*. So we call the helper function once again as *n = 1* and reach our second base case. Because *n = 1*, we return 1. This means store[3] = 2+ 1, so we set the value of 3 in the dictionary to 3.

Next, we return *store[n]* or *3*, which brings us back to *n = 4*, because remember we reached 3 as a result of calling *helper(4-1)*. Now we move to the second helper function, *helper(n-2)*. We call *helper(4-2)* or *helper(2)* again and reach our base case in the if statement above. *helper(n-2)* returns 2, so now store[4] = 3 + 2. The value of the 4 key in the *store* dictionary is 5.

We return *store[4]*. So finally *n = 5* once again. Now, on to *helper(n-2)* as we’ve already calculated *helper(n-1)* for 5 (which returned 5). *helper(5-2)* or *helper(3)* is called again. Once called, we get to use our elif statement. *store[n]* or *store[3]*, exists in the dictionary. We return the value of 3 as we have already calculated it previously. store[5] = 5 + 3.

#### The amount of ways to reach staircase number 5 (n) is 8.

Finally, we return our result for the outer function with n. I’ve also added a call statement below, for you to run the program.