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.
ColorfulCode's Journey 